Swap

                                                                            Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)                                                                                                        Total Submission(s): 3206    Accepted Submission(s): 1161                                                                                                                                            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   Source 2009 Multi-University Training Contest 1 - Host by TJU   Recommend gaojie  

题意： 给你一个N*N的01矩阵，问经过怎样的交换才能使得所有对角线上的值都为1，每次交换只能交换任意的行或列。若无法交换成功则输出-1 解题思路：首先要确定一点，其实可以考虑只交换行或只交换列，比如若只交换列，行其实不管交不交换都是没影响的。把一个图做一次二分匹配，所有的列都匹配到了一个行。若是最大匹配数不能到达n，则说明无论怎么交换都是不能得到对角线全部为1。匹配完成后，再看每行的匹配值，若是x[i] != i，则进行交换

#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <queue> #include <vector> #include <set> #include <stack> #include <map> #include <climits> #include <functional> using namespace std; #define LL long long const int INF=0x3f3f3f3f; int n; int x[125],y[125]; int visit[125]; int mp[125][125]; int ansx[10009],ansy[10009]; bool path(int k) { for(int i=1;i<=n;i++) { if(!visit[i]&&mp[k][i]) { visit[i]=1; if(y[i]==-1||path(y[i])) { y[i]=k; x[k]=i; return 1; } } } return 0; } void MaxMatch() { int ans=0; memset(x,-1,sizeof x); memset(y,-1,sizeof y); for(int i=1;i<=n;i++) { if(x[i]==-1) { memset(visit,0,sizeof visit); if(path(i)) ans++; else break; } } if(ans<n) {printf("-1\n");return ;} int cnt=0; for(int i=1;i<=n;i++) { if(x[i]==i) continue; else cnt++; for(int j=i+1;j<=n;j++) { if(x[j]==i) { ansx[cnt]=i; ansy[cnt++]=x[i]; x[j]=x[i]; break; } } } printf("%d\n",cnt); for(int i=0;i<cnt;i++) printf("C %d %d\n",ansx[i],ansy[i]); } int main() { while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&mp[i][j]); MaxMatch(); } return 0; }