注册登录

洛谷P1894 [USACO4.2]完美的牛栏The Perfect Stall题解

题目

二分图最大匹配问题

cow数组标现在牛栏里的牛是几号牛

每次寻找都要清空vis数组

如果可行有两种情况

1.这个牛栏里没有牛

2.这个牛栏里的牛可以到别的牛栏去

根据此递归即可

Code：


#include <cstring>
#include <iostream>
using namespace std;
const int N = 250;
int cow[N], m, ans, n, p, q; 
bool mp[N][N], vis[N];
int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') w = -1; ch = getchar();}
    while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();}
    return s * w;
}
bool find(int x) {
    for(int i = 1; i <= m; i++) {
        if(mp[x][i] && !vis[i]) {
            vis[i] = 1; 
            if(!cow[i] || find(cow[i])) {cow[i] = x; return 1;}
        }
    }
    return 0;
}
int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; i++) {
        p = read();
        for(int j = 1; j <= p; j++)
            q = read(), mp[i][q] = 1;
    }
    for(int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        if(find(i)) ans++;
    }
    printf("%d\n", ans);
    return 0;
}
知识兔

谢谢收看， 祝身体健康！

计算机