90分求助
查看原帖
90分求助
254733
Night_Bringer楼主2020/11/30 21:29

90分求助

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
void Quick_Read(int &N) {
	N = 0;
	char c = getchar();
	int op = 1;
	while(c < '0' || c > '9') {
		if(c == '-')
			op = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		N = (N << 1) + (N << 3) + c - 48;
		c = getchar();
	}
	N *= op;
}
const int MAXN = 5e2 + 5;
vector<int> v[MAXN];
bool vis[MAXN], twin[MAXN];
int n, m, e;
bool Hungary(int now) {
	int SIZ = v[now].size();
	for(int i = 0; i < SIZ; i++) {
		int next = v[now][i];
		if(!vis[next]) {
			vis[next] = true;
			if(!twin[next] || Hungary(twin[next])) {
				twin[next] = now; 
				return true;
			}
		}
	}
	return false;
}
int Match() {
	int res = 0;
	for(int i = 1; i <= n; i++) {
		memset(vis, 0, sizeof(vis));
		if(Hungary(i))
			res++;
	}
	return res;
}
void Read() {
	int A, B;
	Quick_Read(n);
	Quick_Read(m);
	Quick_Read(e);
	for(int i = 1; i <= e; i++) {
		Quick_Read(A);
		Quick_Read(B);
		v[A].push_back(B);
	}
}
int main() {
	Read();
	printf("%d", Match());
	return 0;
}
2020/11/30 21:29
加载中...