题面
传送门
分析
游戏的操作有以下性质:
1. 如果两个格子在同一列, 那么无论如何操作, 这两个格子都在同一列.
2. 如果两个格子在同一行, 那么无论如何操作, 这两个格子都在同一行.
3. 可以通过操作改变改点在对应行和列中的位置.
我们发现对于第 i 行, 我们必须要找到某一列上的黑格子挪过来放在对角线上, 相当于每一行必须和每一列一一对应
所以对于黑格子 (i,j), 我们将 i 向 j 连边, 跑二分图匹配
如果答案为 n 则有解, 否则无解
代码
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #define maxm 100005
- #define maxn 100005
- using namespace std;
- int t,n;
- struct edge{
- int from;
- int to;
- int next;
- }E[maxm];
- int head[maxn];
- int sz=0;
- void add_edge(int u,int v){
- // printf("%d %d\n",u,v);
- sz++;
- E[sz].from=u;
- E[sz].to=v;
- E[sz].next=head[u];
- head[u]=sz;
- }
- int vis[maxn];
- int match[maxn];
- int dfs(int x,int t){
- for(int i=head[x];i;i=E[i].next){
- int y=E[i].to;
- if(vis[y]<t){
- vis[y]=t;
- if(!match[y]||dfs(match[y],t)){
- match[y]=x;
- return 1;
- }
- }
- }
- return 0;
- }
- int hungary(){
- memset(vis,0,sizeof(vis));
- memset(match,0,sizeof(match));
- int ans=0;
- for(int i=1;i<=n*2;i++){
- if(dfs(i,i)) ans++;
- else break;
- }
- return ans;
- }
- void INI(){
- sz=0;
- memset(E,0,sizeof(E));
- memset(head,0,sizeof(head));
- }
- int main(){
- int x;
- scanf("%d",&t);
- for(int cas=1;cas<=t;cas++){
- scanf("%d",&n);
- INI();
- for(int i=1;i<=n;i++){
- for(int j=1;j<=n;j++){
- scanf("%d",&x);
- if(x==1) add_edge(i,j+n);
- }
- }
- if(hungary()==n) printf("Yes\n");
- else printf("No\n");
- }
- }
来源: http://www.bubuko.com/infodetail-2902187.html