二分图WA求调
查看原帖
二分图WA求调
1270559
zkhehe楼主2024/10/7 16:29

稍微借鉴了点题解,不过还是wa。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k,a,b;
vector<int>vc[205];
int mth[205];
int ans;
int vis[205][205],visc=0;
bool dfs(int u){
	for(int v:vc[u]){
		if(vis[v][visc])continue;
		vis[v][visc]=1;
		if(mth[v]==0||dfs(mth[v])){
			mth[v]=u;
			mth[u]=v;
			return true;
		}
	}
	return false;
}
signed main(){
	while(true){
		ans=0;
		memset(mth,0,sizeof mth);
		memset(vis,0,sizeof vis);
		for(int i=1;i<=n;i++){
			while(vc[i].size()){
				vc[i].pop_back();
			}
		}
		scanf("%lld",&n);
		if(n==0)break;
		scanf("%lld%lld",&m,&k);
		int _;
		for(int i=1;i<=k;i++){
			scanf("%lld",&_);
			scanf("%lld%lld",&a,&b);
			if(a==0||b==0)continue;
			vc[a].push_back(b+n);
			vc[b+n].push_back(a);
		}
		for(int i=1;i<=n;i++){
			vis[i][visc]=1;
			if(dfs(i))ans++;
			visc++;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

2024/10/7 16:29
加载中...