C++14(g++5.4) 解法, 执行用时: 11ms, 内存消耗: 444K, 提交时间: 2020-07-18 08:43:26

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m, t, ans, fa[205];
bool a[205][205], v[205];

bool dfs(int x) {
	for (int y = 1; y <= m; y++) {
		if (v[y] || a[x][y]) continue;
		v[y] = 1;
		if (fa[y] == 0 || dfs(fa[y])) {
			fa[y] = x;
			return true;
		}
	}
	return false;
}

int main() {
	cin >> n >> m >> t;
	for (int i = 1; i <= t; i++) {
		int x, y; cin >> x >> y;
		a[x][y] = 1;
	}
	for (int i = 1; i <= n; i++) {
		memset(v, 0, sizeof(v));
		if (dfs(i)) ans++;
	}
	cout << ans << endl;
}

C++ 解法, 执行用时: 16ms, 内存消耗: 524K, 提交时间: 2022-04-11 16:09:10

#include<bits/stdc++.h>
using namespace std;
int mp[205][205],vis[205],fa[205],n,m,t,a,b,ans;
bool dfs(int x){
	for(int y=1;y<=m;y++){
		if(vis[y]||mp[x][y])continue;
		vis[y]=1;
		if(!fa[y]||dfs(fa[y])){fa[y]=x;return 1;}
	}
	return 0;
}
int main(){
	cin>>n>>m>>t;
	while(t--)cin>>a>>b,mp[a][b]=1;
	for(int x=1;x<=n;x++){
		memset(vis,0,sizeof vis);
		if(dfs(x))ans++;
	}
	cout<<ans;
	return 0;
}