二分图80分WA on #6#7求助
查看原帖
二分图80分WA on #6#7求助
609439
zyh_helen楼主2023/1/9 15:53
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#define int long long
using namespace std;
const int N = 2e2 + 10;
int n, p, q, ans;
bool link1[N][N], vis1[N], link2[N][N], vis2[N];
int match1[N], match2[N], lmh1[N], lmh2[N];
bool find1(int x){
	for(int i = 1;i <= p;i++){
		if(!vis1[i] && link1[x][i]){
			vis1[i] = 1;
			if(!match1[i] || find1(match1[i])){
				match1[i] = x;
				return 1;
			}
		}
	}
	return 0;
}
bool find2(int x){
	for(int i = 1;i <= q;i++){
		if(!vis2[i] && link2[x][i]){
			vis2[i] = 1;
			if(!match2[i] || find2(match2[i])){
				match2[i] = x;
				return 1;
			}
		}
	}
	return 0;
}
signed main(){
	cin >> n >> p >> q;
	for(int i = 1;i <= n;i++){
		int f, d;
		scanf("%lld%lld", &f, &d);
		for(int j = 1;j <= f;j++){
			int x;
			scanf("%lld", &x);
			link1[i][x] = 1;
		}
		for(int j = 1;j <= d;j++){
			int x;
			scanf("%lld", &x);
			link2[i][x] = 1;
		}
	}
	for(int i = 1;i <= n;i++){
		memset(vis1, 0, sizeof(vis1));
		memset(vis2, 0, sizeof(vis2));
		memcpy(lmh1, match1, sizeof(lmh1));
		memcpy(lmh2, match2, sizeof(lmh2));
		if(find1(i) && find2(i))ans++;
		else {
			memcpy(match1, lmh1, sizeof(lmh1));
			memcpy(match2, lmh2, sizeof(lmh2));
		}
	}
	cout << ans;
	return 0;
}
2023/1/9 15:53
加载中...