陷入了死循环
#include<bits/stdc++.h>
using namespace std;
int a[201*2][201*2]; //邻接矩阵+初始状态
int b[201*2]; //该点是否被访问过
int b2[201*2]; //该点是否为匹配点
bool c[201*2][201*2]; //该边是否为匹配边
int countl=0;
int nn;
int t;
inline int find(int start,int k,int last,bool w) //寻找增广路(开始点,当前点,上一个点 ,需要寻找匹配路?非匹配路?)
{
if(b2[start]) //如果开始点为匹配点,返回
return 0;
if(b2[k]==0&&k!=start) //如果不是初始点并且是非匹配点,找到增广路返回。
{
c[k][last]=1; //该边成为匹配边//无向
// cout<<start<<' '<<k<<' '<<last<<' '<<w<<"find it"<<endl;
c[last][k]=1;
b2[k]=1; //该点成为匹配点
countl+=2;
return 1;
}
for(int i=1;i<=nn*2;i++)
{
// printf("%d %d ",t,i);
// cout<</*t<<' '<<start<<*/' '<<k<<' '<<last<<' '<<w<<' '<<i<<endl;
if(i!=k&&c[k][i]==w&&a[k][i]&&b[i]&&i!=start) //如果这个点不是当前点并且该边符合要求并且该点没有访问过
{
b[i]=0;
if(find(start,i,k,!w))
{
c[k][last]=w; //无向
c[last][k]=w;
b2[k]=1;
return 1;
// flag=1;
}
b[i]=1;
}
}
return 0;
}
bool dfs(int n)
{
int flag=1;
while(flag)
{
flag=0;
for(int i=1;i<=n;i++)
{
b[i]=0;
if(find(i,i,i,0))
{
flag=1;
b2[i]=1;
}
b[i]=1;
}
memset(b,1,sizeof(b));
}
if(countl==n)
return 1;
return 0;
}
int main()
{
freopen("a.txt","r",stdin);
freopen("b2.txt","w",stdout);
cin>>t;
while(t--)
{
memset(b,1,sizeof(b));
memset(c,-1,sizeof(c));
memset(b2,0,sizeof(b2));
memset(a,0,sizeof(a));
scanf("%d",&nn);
if(nn==1)
{
int a;
cin>>a;
if(a)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
continue;
}
else if(nn==2)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
if((a==1&&d==1)||(b==1&&c==1))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
continue;
}
/* if(nn==3)
countl++;*/
else
{
for(int i=1;i<=nn;i++)
for(int j=1;j<=nn;j++)
{
scanf("%d",&a[i][nn+j]);
a[nn+j][i]=a[i][nn+j]; //无向
if(a[i][nn+j]==1)
{
c[i][nn+j]=0;
c[nn+j][i]=0; //无向
}
}
if(dfs(nn*2))
printf("Yes\n");
else
printf("No\n");
}
// cout<<countl<<endl;
countl=0;
}
return 0;
}
不要在意众多的调试语句
也不要告诉我提交的时候不能feopen(我是去掉提交的)
#include<bits/stdc++.h>
using namespace std;
int a[201*2][201*2]; //邻接矩阵+初始状态
int b[201*2]; //该点是否被访问过
int b2[201*2]; //该点是否为匹配点
bool c[201*2][201*2]; //该边是否为匹配边
int countl=0;
int nn;
int t;
inline int find(int start,int k,int last,bool w) //寻找增广路(开始点,当前点,上一个点 ,需要寻找匹配路?非匹配路?)
{
if(b2[start]) //如果开始点为匹配点,返回
return 0;
if(b2[k]==0&&k!=start) //如果不是初始点并且是非匹配点,找到增广路返回。
{
c[k][last]=1; //该边成为匹配边//无向
// cout<<start<<' '<<k<<' '<<last<<' '<<w<<"find it"<<endl;
c[last][k]=1;
b2[k]=1; //该点成为匹配点
countl+=2;
return 1;
}
for(int i=1;i<=nn*2;i++)
{
// printf("%d %d ",t,i);
// cout<</*t<<' '<<start<<*/' '<<k<<' '<<last<<' '<<w<<' '<<i<<endl;
if(i!=k&&c[k][i]==w&&a[k][i]&&b[i]&&i!=start) //如果这个点不是当前点并且该边符合要求并且该点没有访问过
{
b[i]=0;
if(find(start,i,k,!w))
{
c[k][last]=w; //无向
c[last][k]=w;
b2[k]=1;
return 1;
// flag=1;
}
b[i]=1;
}
}
return 0;
}
bool dfs(int n)
{
int flag=1;
while(flag)
{
flag=0;
for(int i=1;i<=n;i++)
{
b[i]=0;
if(find(i,i,i,0))
{
flag=1;
b2[i]=1;
}
b[i]=1;
}
memset(b,1,sizeof(b));
}
if(countl==n)
return 1;
return 0;
}
int main()
{
freopen("a.txt","r",stdin);
freopen("b2.txt","w",stdout);
cin>>t;
while(t--)
{
memset(b,1,sizeof(b));
memset(c,-1,sizeof(c));
memset(b2,0,sizeof(b2));
memset(a,0,sizeof(a));
scanf("%d",&nn);
if(nn==1)
{
int a;
cin>>a;
if(a)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
continue;
}
else if(nn==2)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
if((a==1&&d==1)||(b==1&&c==1))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
continue;
}
/* if(nn==3)
countl++;*/
else
{
for(int i=1;i<=nn;i++)
for(int j=1;j<=nn;j++)
{
scanf("%d",&a[i][nn+j]);
a[nn+j][i]=a[i][nn+j]; //无向
if(a[i][nn+j]==1)
{
c[i][nn+j]=0;
c[nn+j][i]=0; //无向
}
}
if(dfs(nn*2))
printf("Yes\n");
else
printf("No\n");
}
// cout<<countl<<endl;
countl=0;
}
return 0;
}
不要在意众多的调试语句
也不要告诉我提交的时候不能feopen(我是去掉提交的)