80分求助
查看原帖
80分求助
119638
xia0ji233楼主2022/2/4 03:54

看是1点看的,实在想不到办法了,求助一下,这个代码的问题在哪,感激不尽。

#include<bits/stdc++.h>
using namespace std;
struct eee{
	int to;
	int next;
}edge[50000];
int cnt,n,root[501],check[500],match[500];
void add(int x,int y){
	//printf("%d %d\n",x,y);
	edge[++cnt].to=y;
	edge[cnt].next=root[x];
	root[x]=cnt;
}
int dfs(int u){
	for(int i=root[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(!check[v]){
			check[v]=true;
			if(!match[v]||dfs(match[v])){
				match[u]=v;
				match[v]=u;
				//printf("check\n");
				return true; 
			}
		}
	}
	return false;
}
int xyl(){
	int ans=0;
	for(int i=1;i<=n;i++){
		if(!match[i]){
			memset(check,0,sizeof(check));
			if(dfs(i))ans++;
			
		}
		// for(int i=1;i<=2*n;i++){
			
		// ;	printf("%d ",match[i]);
		// }
		//putchar(10);
	}
	return ans;
}
void solve(){
	cin>>n;
	memset(root,0,sizeof(root));
	memset(match,0,sizeof(match));
	cnt=0;
	string s;
	getchar();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int x;
			cin>>x;
			if(x==1){
				add(i,j+n);
				add(j+n,i);
			}
		}
	}
	//printf("%d\n",dfs(41));
	if(xyl()==n){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	for(int i=1;i<=n*2;i++){
	//	if(match[i]==0)printf("%d ",i);
	;	//printf("%d ",match[i]);
	}
	
	
}
int main(){
	freopen("1.in","r",stdin);
	int t;
	cin>>t;
	while(t--)solve();
	
	return 0;
}
2022/2/4 03:54
加载中...