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”.
//在N*N的方格中选 N个 行列不同的点、 然后把这些点排个顺序
// 在N*N的方格中选 N个 行列不同的点 -->明显的二分图匹配模型
#include <iostream> #include <vector> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N=110; bool visit[N]; int match[N]; vector <int> G[N]; int rc[N][2]; bool dfs(int u) { int i,v; for(i=0;i<G[u].size();i++) { v=G[u][i]; if(!visit[v]) { visit[v]=true; if(!match[v]||dfs(match[v])) { match[v]=u; return true; } } } return false; } int main() { int n,m; while(scanf("%d",&n)!=EOF) { int i,j; for(i=1;i<=n;i++) for(G[i].clear(),j=1;j<=n;j++) { scanf("%d",&m); if(m) G[i].push_back(j); } int ans=0; memset(match,0,sizeof(match)); for(i=1;i<=n;i++) { memset(visit,0,sizeof(visit)); if(dfs(i)) ans++; } if(ans!=n) { printf("-1\n");continue;} m=0; for(i=1;i<n;i++) if(match[i]!=i) { for(j=i+1;j<=n;j++) if(match[j]==i) { m++; rc[m][0]=match[j]; rc[m][1]=match[i]; match[j]=match[i]; } } printf("%d\n",m); for(i=1;i<=m;i++) printf("R %d %d\n",rc[i][0],rc[i][1]); } return 0; }