【蒟蒻求助】刚学二分图,卡46分了
查看原帖
【蒟蒻求助】刚学二分图,卡46分了
378520
河上的九酱楼主2021/2/7 09:27
#include<bits/stdc++.h>
#define N 520
using namespace std;
int mmap[N][N],n,m,vis[N],pre[N];
int dfs(int x) {

	for(int i=n+1; i<=n+n; i++) {
		if(!vis[i]&&mmap[x][i]) {
			vis[i]=1;
			if(pre[i]==-1||dfs(pre[i])) {
				pre[i]=x;
				return 1;
			}
		}
	}
	return 0;
}
int main() {
	char t;
	while(cin>>n>>m) {
		memset(mmap,0,sizeof(mmap));
		memset(pre,-1,sizeof(pre));
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=m; j++) {
				cin>>t;
				if(t=='*') {
					mmap[i][m+j]=1;
				}
			}

		}
		int ans=0;
		for(int i=1; i<=n; i++) {
			memset(vis,0,sizeof(vis));
			ans+=dfs(i);
		}
		cout<<ans<<endl;
	}
	return 0;
}
2021/2/7 09:27
加载中...