题意: 矩阵游戏在一个 N*N 黑白方阵进行. 每次可以对该矩阵进行两种操作:
行交换操作: 选择矩阵的任意两行, 交换这两行(即交换对应格子的颜色)
列交换操作: 选择矩阵的任意行列, 交换这两列(即交换对应格子的颜色)
游戏的目标, 即通过若干次操作, 使得方阵的主对角线 (左上角到右下角的连线) 上的格子均为黑色.
要求判断是否有解
n<=200
思路: 原先同行或同列的格子后依旧同行或同列
转化为是否能找到 n 个行列互不相同的点
行列建边后跑二分图最大匹配即可
- #include<cstdio>
- #include<cstring>
- #include<string>
- #include<cmath>
- #include<iostream>
- #include<algorithm>
- #include<map>
- #include<set>
- #include<queue>
- #include<vector>
- using namespace std;
- typedef long long ll;
- typedef unsigned int uint;
- typedef unsigned long long ull;
- typedef pair<int,int> PII;
- typedef vector<int> VI;
- #define fi first
- #define se second
- #define MP make_pair
- #define N 110000
- #define M 410000
- #define eps 1e-8
- #define pi acos(-1)
- #define oo 1e9
- int head[N],vet[N],nxt[N],match[N],flag[N],tot;
- void add(int a,int b)
- {
- nxt[++tot]=head[a];
- vet[tot]=b;
- head[a]=tot;
- }
- int dfs(int u)
- {
- flag[u]=1;
- int e=head[u];
- while(e)
- {
- int v=vet[e];
- if(!match[v]||!flag[match[v]]&&dfs(match[v]))
- {
- match[v]=u;
- return 1;
- }
- e=nxt[e];
- }
- return 0;
- }
- int main()
- {
- int cas;
- scanf("%d",&cas);
- while(cas--)
- {
- int n;
- scanf("%d",&n);
- memset(head,0,sizeof(head));
- memset(match,0,sizeof(match));
- tot=0;
- 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 ans=0;
- for(int i=1;i<=n;i++)
- {
- memset(flag,0,sizeof(flag));
- if(dfs(i)) ans++;
- }
- //printf("%d\n",ans);
- if(ans==n) printf("Yes\n");
- else printf("No\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2816489.html