侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【匈牙利算法】完美牛棚

GabrielxD
2022-12-31 / 0 评论 / 0 点赞 / 94 阅读 / 874 字
温馨提示:
本文最后更新于 2023-03-16,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1394. 完美牛棚 - AcWing题库


农夫约翰上周刚刚建好了新的牛棚,并引进了最新的挤奶技术。

不幸的是,由于工程问题,牛棚中的每个单间都不太一样。

第一周,约翰将奶牛们随机分配在了各个单间中。

但是很快他就发现,每头奶牛都只愿意在一部分自己喜欢的单间中产奶。

在过去的一周中,农夫约翰一直在收集有关哪些奶牛愿意在哪些单间产奶的数据。

一个单间只能分配给一头奶牛,当然,一头奶牛也可能只愿意在一个单间中产奶。

给定奶牛的住宿喜好,请你计算,通过合理分配奶牛的住所,最多能够让多少奶牛可以住在自己愿意产奶的单间中。

输入格式

第一行包含两个整数 NNMM ,分别表示奶牛的数量以及单间的数量。

接下来 NN 行,每行记录一个奶牛愿意产奶的单间信息。首先包含一个整数 SiS_i ,表示这头奶牛愿意在 SiS_i 个单间中产奶。接下来包含 SiS_i不同的整数,表示这些单间的编号。

所有单间的编号为 1M1 \sim M

输出格式

输出一个整数,表示可以被分配在自己愿意产奶的单间中的奶牛的最大数量。

数据范围

0N,M2000 \le N,M \le 200
0SiM0 \le S_i \le M

输入样例:

5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2

输出样例:

4

解题

方法一:匈牙利算法

思路

求二分图最大匹配裸题,详见匈牙利算法求二分图最大匹配

代码

import java.util.*;
import java.io.*;

public class Main {
    static int n, m, N, M;
    static int[] h, e, ne;
    static int idx;
    static int[] matchs;
    static boolean[] vis;
    
    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a] ;
        h[a] = idx++;
    }
    
    static boolean find(int u) {
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (!vis[v]) {
                vis[v] = true;
                if (matchs[v] == 0 || find(matchs[v])) {
                    matchs[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        in.nextToken();
        m = (int) in.nval;
        N = Math.max(n, m) + 1;
        M = m * m;
        h = new int[N];
        Arrays.fill(h, -1);
        e = new int[M];
        ne = new int[M];
        for (int u = 1; u <= n; ++u) {
            in.nextToken();
            int s = (int) in.nval;
            while (s-- > 0) {
                in.nextToken();
                int v = (int) in.nval;
                add(u, v);
            }
        }
        matchs = new int[N];
        vis = new boolean[N];
        int ans = 0;
        for (int u = 1; u <= n; ++u) {
            Arrays.fill(vis, false);
            if (find(u)) ++ans;
        }
        System.out.println(ans);
    }
}
#include <iostream>
#include <cstring>

using namespace std;

const int N = 210, M = N * N;
int n1, n2, heads[M], vals[M], nexts[M], idx;
int matchs[N];
bool vis[N];

void add(int a, int b) {
    vals[idx] = b, nexts[idx] = heads[a], heads[a] = idx++;
}

bool find(int u) {
    for (int i = heads[u]; i != -1; i = nexts[i]) {
        int v = vals[i];
        if (!vis[v]) {
            vis[v] = true;
            if (!matchs[v] || find(matchs[v])) {
                matchs[v] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {
    memset(heads, -1, sizeof(heads));
    scanf("%d%d", &n1, &n2);
    for (int u = 1; u <= n1; ++u) {
        int k, v;
        scanf("%d", &k);
        while (k--) {
            scanf("%d", &v);
            add(u, v);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n1; ++i) {
        memset(vis, false, sizeof(vis));
        if (find(i)) ++ans;
    }
    printf("%d\n", ans);

    return 0;
}
0

评论区