BZOJ1059:[ZJOI2007]矩陣游戲

1059: [ZJOI2007]矩陣游戲

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1726 Solved: 835
[Submit][Status]

Description

小Q是一個非常聰明的孩子，除了國際象棋，他還很喜歡玩一個電腦益智游戲——矩陣游戲。矩陣游戲在一個N*N黑白方陣進行（如同國際象棋一般，只是顏色是隨意的）。每次可以對該矩陣進行兩種操作：行交換操作：選擇矩陣的任意兩行，交換這兩行（即交換對應格子的顏色）列交換操作：選擇矩陣的任意行列，交換這兩列（即交換對應格子的顏色）游戲的目標，即通過若干次操作，使得方陣的主對角線(左上角到右下角的連線)上的格子均為黑色。對於某些關卡，小Q百思不得其解，以致他開始懷疑這些關卡是不是根本就是無解的！！於是小Q決定寫一個程序來判斷這些關卡是否有解。

Input

第一行包含一個整數T，表示數據的組數。接下來包含T組數據，每組數據第一行為一個整數N，表示方陣的大小；接下來N行為一個N*N的01矩陣（0表示白色，1表示黑色）。

Output

輸出文件應包含T行。對於每一組數據，如果該關卡有解，輸出一行Yes；否則輸出一行No。

Sample Input

2
2
0 0
0 1
3
0 0 1
0 1 0
1 0 0

Sample Output

No
Yes
【數據規模】
對於20%的數據，N ≤ 7
對於50%的數據，N ≤ 50
對於100%的數據，N ≤ 200 同行同列的點無論經過多少次變換人仍然同行或同列，所以問題轉換為從黑色格子裡面選出N個，使它們的X坐標和Y坐標互不相同。
很容易想到二分圖匹配，左邊為x坐標，右邊是y坐標，若(x,y)為黑格子，則由x向y連一條邊。 然後求最大匹配，若最大匹配為n，則此關卡有解，否則無解

#include
#include
#include
#include
using namespace std;
struct node{
       int next,to;
       }e[40010];
int match[410],p[410],T,i,j,n,tot;
bool visit[410];
void add(int u,int v)
{
     e[++tot].to=v;
     e[tot].next=p[u];
     p[u]=tot;
}
bool dfs(int u)
{
     for (int i=p[u]; i!=0; i=e[i].next)
     {
         int v=e[i].to;
         if (!visit[v])
         {
             visit[v]=true;
             if (match[v]==0 || dfs(match[v]))
             {
                 match[v]=u;
                 return true;
             }
         }
     }
     return false;
} 
int main()
{
    scanf("%d",&T);
    while (T--)
    {
          tot=0;
          memset(match,0,sizeof(match));
          memset(p,0,sizeof(p));
          scanf("%d",&n);
          for (i=1; i<=n; i++)
              for (j=1; j<=n; j++)
              {
                  int c;
                  scanf("%d",&c);
                  if (c==1) add(i,j+n);
              }
          for (i=1; i<=n; i++)
          {
              memset(visit,false,sizeof(visit));
              if (!dfs(i))  break;
          }
          if (i>n)  printf("Yes\n"); else printf("No\n");
    }
}