匈牙利算法.md

tags	title	created	modified
Code	匈牙利算法	2022-09-02T13:08:10.159Z	2022-09-02T13:08:29.188Z

匈牙利算法

int con[510][510];
int vis[510];
int link[510];
int n, m, k;

int find(int x)
{
	for (int i = 1; i <= m; i++){
		if (vis[i] == 0 && con[x][i] == 1){
			vis[i] = 1;
			if (link[i] == -1 || find(link[i])){
				link[i] = x;
				return 1;
			}
		}
	}
	return 0;
}
int hungary()
{
	int res = 0;
	memset(link, -1, sizeof(link));
	for (int x = 1; x <= n; x++) {
		memset(vis, 0, sizeof(vis));
		if (find(x))res++;
	}
	return res;
}
void solve()
{
    memset(con,0,sizeof(con));
    cin>>n>>m>>k;
    int x,y;
    for(int i=1;i<=k;i++){
        cin>>x>>y;
        con[x][y]=1;
    }
    cout<<hungary()<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int tt;
    while(tt--)solve();
    return 0;
}