HDU2819--Swap

Swap
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 972 Accepted Submission(s): 312
Special Judge

Problem Description
Given an N*N matrix with each entry equal to 0 or 1. You can swap any two rows or any two columns. Can you find a way to make all the diagonal entries equal to 1?

Input
There are several test cases in the input. The first line of each test case is an integer N (1 <= N <= 100). Then N lines follow, each contains N numbers (0 or 1), separating by space, indicating the N*N matrix.

Output
For each test case, the first line contain the number of swaps M. Then M lines follow, whose format is “R a b” or “C a b”, indicating swapping the row a and row b, or swapping the column a and column b. (1 <= a, b <= N). Any correct answer will be accepted, but M should be more than 1000.

If it is impossible to make all the diagonal entries equal to 1, output only one one containing “-1”.

Sample Input
2
0 1
1 0
2
1 0
1 0

Sample Output
1
R 1 2
-1

最大匹配

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cmath>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<cstring>
  7 using namespace std;
  8 
  9 int Link[1001][1001];
 10 int mk[1010];
 11 int cy[1010];
 12 int num[1001];
 13 int clo[1001];
 14 int cx[1011];
 15 int n;
 16 struct node
 17 {
 18     int x,y;
 19 };
 20 
 21 void init()
 22 {
 23     memset(Link,0,sizeof(Link));
 24     memset(mk,0,sizeof(mk));
 25     memset(num,0,sizeof(num));
 26     memset(cy,0xff,sizeof(num));
 27     memset(cx,0xff,sizeof(cx));
 28     memset(clo,0,sizeof(clo));
 29 }
 30 
 31 int path(int u)
 32 {
 33     int v;
 34     for(v=1;v<=n;v++)
 35     {
 36         if(!mk[v]&&Link[u][v])
 37         {
 38             mk[v]=1;
 39             if(cy[v]==-1||path(cy[v]))
 40             {
 41                 cx[u]=v;
 42                 cy[v]=u;
 43                 return 1;
 44             }
 45         }
 46     }
 47     return 0;
 48 }
 49 
 50 int maxmatch()
 51 {
 52     int i;
 53     int sum=0;
 54     for(i=1;i<=n;i++)
 55     {
 56         if(cx[i]==-1)
 57         {
 58             memset(mk,0,sizeof(mk));
 59             sum+=path(i);
 60         }
 61     }
 62     return sum;
 63 }
 64 
 65 int main()
 66 {
 67     while(scanf("%d",&n)!=EOF)
 68     {
 69         int i,j;
 70         init();
 71         for(i=1;i<=n;i++)
 72         {
 73             for(j=1;j<=n;j++)
 74             {
 75                 scanf("%d",&Link[i][j]);
 76             }
 77         }
 78         int ans=maxmatch();
 79         if(ans<n){
 80             printf("-1
");
 81             continue;
 82         }
 83         queue<node>Q;
 84         int sum=0;
 85         for(i=1;i<=n;i++)
 86         {
 87             if(cx[i]!=i)
 88             {
 89                 for(j=i+1;j<=n;j++)
 90                 {
 91                     if(cx[j]==i)
 92                     {
 93                         cx[j]=cx[i];
 94                         cx[i]=i;
 95                         node t;
 96                         t.x=i,t.y=j;
 97                         Q.push(t);
 98                         sum++;
 99                         break;
100                     }
101                 }
102             }
103         }
104         printf("%d
",sum);
105         while(!Q.empty())
106         {
107             node head=Q.front();
108             Q.pop();
109             printf("R %d %d
",head.x,head.y);
110         }
111     }
112     return 0;
113 }

View Code