题解:
游戏目标要求通过交换行或者交换列，最终使得主对角线全部为1，即黑色。
行转为男生，列转为女生，如果g[i][j] = 1,那么说明男生i和女生j有关系，则题目通关要求转为最大匹配能否达到n（n为矩阵大小)
我犯的错误：
- 在found函数里面更新match数组，match数组应该在每一次测试数据输入之前更新，used数组才是在found函数里面更新
- 考虑成无向图，而且***得直接令g[j][i] = g[i][j] = 1,这不是将矩阵直接赋值为1吗，我太憨憨了
- 真的太菜了，要努力呀
AC代码
邻接表存图
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N = 210;
int g[210][210];
int used[N],match[N];
int n;
int found(int x)
{
for(int j=1; j<=n; j++)
{
if(g[x][j]&&!used[j])
{
used[j] = 1;
if(!match[j]||found(match[j]))
{
match[j] = x;
return 1;
}
}
}
return 0;
}
int main()
{
int t;
cin>>t;
while(t--)
{
//match和邻接矩阵要在这里清零，不能在found数组里面
mem(match ,0);
mem(g,0);
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
scanf("%d",&g[i][j]);
// g[j][i] = g[i][j] = 1;
}
}
int res = 0;
//对于每一行，看能否找到匹配
for(int i=1; i<=n; i++)
{
mem(used,0);
if(found(i)) res++;
}
// cout<<res<<endl;
if(res==n) puts("Yes");
else puts("No");
}
return 0;
}
邻接表存图
这里有几点要注意：
第一，每次记得初始化数组，和idx
第二，数组e和ne要开到N*N,开小了竟然返回得是TLE,奇葩判断
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N = 220;
int e[N*N],ne[N*N];
int h[N],idx;
int used[N],match[N];
int n;
void add(int a,int b)
{
e[idx] = b;
//采用头插法
ne[idx] = h[a];
h[a] = idx++;
}
int found(int x)
{
for(int i=h[x]; i!=-1; i=ne[i])
{
int j = e[i];//邻接表这里存得是列号
if(!used[j])
{
used[j] = 1;
if(match[j]==0||found(match[j]))
{
match[j] = x;
return 1;
}
}
}
return 0;
}
int main()
{
int t;
cin>>t;
while(t--)
{
//match和邻接表要在这里清零，不能在found数组里面
mem(e,0);
mem(ne,0);
mem(match,0);
mem(h,-1);//初始化透指针，指向-1，-1代表空
idx = 0;//注意这里idx要更新为0
memset(match, 0,sizeof match);
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
int x;
scanf("%d",&x);
if(x) add(i,j);
}
}
int res = 0;
//对于每一行，看能否找到匹配
for(int i=1; i<=n; i++)
{
mem(used ,0);
if(found(i)) res++;
}
if(res==n) puts("Yes");
else puts("No");
}
return 0;
}
京公网安备 11010502036488号