BZOJ 1059 [ZJOI2007]矩阵游戏：二分图匹配

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1059

题意：

　　给你一个n*n的01矩阵。

　　你可以任意次地交换某两行或某两列。

　　问你是否可以让这个矩阵的主对角线(左上角到右下角的连线)上的格子均为黑色。

题解：

　　可以发现，对于一个格子，无论怎样移动，它原来行（列）上的格子还是在现在的行（列）上。

　　因为最终目标是将n个黑色格子移到对角线上，所以只要有n个黑色格子的行列均不相同即可。

　　那么对于每个黑色格子，将行号i向列号j连一条边，然后跑二分图匹配，看匹配数是否等于n即可。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <vector>

 #define MAX_N 205

 using namespace std;

 int n,t;

 int vis[MAX_N];

 int match[MAX_N];

 vector<int> edge[MAX_N];

 void read()

 {

     cin>>n;

     for(int i=;i<=n;i++) edge[i].clear();

     int x;

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

     {

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

         {

             cin>>x;

             if(x) edge[i].push_back(j);

         }

     }

 }

 bool hungary(int now,int cnt)

 {

     for(int i=;i<edge[now].size();i++)

     {

         int temp=edge[now][i];

         if(vis[temp]!=cnt)

         {

             vis[temp]=cnt;

             if(match[temp]==- || hungary(match[temp],cnt))

             {

                 match[temp]=now;

                 return true;

             }

         }

     }

     return false;

 }

 void work()

 {

     memset(vis,,sizeof(vis));

     memset(match,-,sizeof(match));

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

     {

         if(!hungary(i,i))

         {

             cout<<"No"<<endl;

             return;

         }

     }

     cout<<"Yes"<<endl;

 }

 int main()

 {

     cin>>t;

     while(t--)

     {

         read();

         work();

     }

 }

巴特西

BZOJ 1059 [ZJOI2007]矩阵游戏：二分图匹配

最新文章

热门文章