【BZOJ1059】矩阵游戏（二分图最大匹配）

题意：矩阵游戏在一个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]=;

     int e=head[u];

     while(e)

     {

         int v=vet[e];

         if(!match[v]||!flag[match[v]]&&dfs(match[v]))

         {

             match[v]=u;

             return ;

         }

         e=nxt[e];

     }

     return ;

 }

 int main()

 {

     int cas;

     scanf("%d",&cas);

     while(cas--)

     {

         int n;

         scanf("%d",&n);

         memset(head,,sizeof(head));

         memset(match,,sizeof(match));

         tot=;

         for(int i=;i<=n;i++)

          for(int j=;j<=n;j++)

          {

              int x;

              scanf("%d",&x);

              if(x) add(i,j);

          }

          int ans=;

          for(int i=;i<=n;i++)

          {

              memset(flag,,sizeof(flag));

              if(dfs(i)) ans++;

          }

          //printf("%d\n",ans);

          if(ans==n) printf("Yes\n");

           else printf("No\n");

     }

     return ;

 }

巴特西

【BZOJ1059】矩阵游戏（二分图最大匹配）

最新文章

热门文章