HDU2819(KB10-E 二分图最大匹配)

Swap

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3800 Accepted Submission(s): 1401
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

按行交换。对行进行1-n编号，对列也进行编号。

若第i行的第j1、j2……列有1，则节点i与j1、j2……连边。

二分图跑最大匹配，为完美匹配方可。

matching数组保存每个点的匹配，模拟一下交换输出答案。

  1 //2017-08-26
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <iostream>
  5 #include <algorithm>
  6 
  7 using namespace std;
  8 
  9 const int N = 100000;
 10 const int M = 5000000;
 11 int head[N], tot;
 12 struct Edge{
 13     int to, next;
 14 }edge[M];
 15 
 16 void init(){
 17     tot = 0;
 18     memset(head, -1, sizeof(head));
 19 }
 20 
 21 void add_edge(int u, int v){
 22     edge[tot].to = v;
 23     edge[tot].next = head[u];
 24     head[u] = tot++;
 25 
 26     edge[tot].to = u;
 27     edge[tot].next = head[v];
 28     head[v] = tot++;
 29 }
 30 
 31 int n;
 32 int matching[N];
 33 int check[N];
 34 bool dfs(int u){
 35     for(int i =  head[u]; i != -1; i = edge[i].next){
 36         int v = edge[i].to;
 37         if(!check[v]){//要求不在交替路
 38             check[v] = 1;//放入交替路
 39             if(matching[v] == -1 || dfs(matching[v])){
 40                 //如果是未匹配点，说明交替路为增广路，则交换路径，并返回成功
 41                 matching[u] = v;
 42                 matching[v] = u;
 43                 return true;
 44             }
 45         }
 46     }
 47     return false;//不存在增广路
 48 }
 49 
 50 //hungarian: 二分图最大匹配匈牙利算法
 51 //input: null
 52 //output: ans 最大匹配数
 53 int hungarian(){
 54     int ans = 0;
 55     memset(matching, -1, sizeof(matching));
 56     for(int u = 1; u <= n; u++){
 57         if(matching[u] == -1){
 58             memset(check, 0, sizeof(check));
 59             if(dfs(u))
 60               ans++;
 61         }
 62     }
 63     return ans;
 64 }
 65 
 66 const int MAXID = 100;
 67 int a[N], b[N], cnt;
 68 
 69 int main()
 70 {
 71     std::ios::sync_with_stdio(false);
 72     //freopen("inputE.txt", "r", stdin);
 73     while(cin>>n){
 74         init();
 75         int v;
 76         for(int i = 1; i <= n; i++){
 77             for(int j = 1; j <= n; j++){
 78                 cin>>v;
 79                 if(v){
 80                     add_edge(i, j+MAXID);
 81                 }
 82             }
 83         }
 84         int match = hungarian();
 85         if(match != n)cout<<-1<<endl;
 86         else{
 87             for(int i = 1; i <= n; i++)
 88                   matching[i]-=100;
 89             cnt = 0;
 90             for(int i = 1; i <= n; i++){
 91                 for(int j = 1; j <= n; j++){
 92                     if(i == j)continue;
 93                     if(matching[j] == i){
 94                         swap(matching[i], matching[j]);
 95                         a[cnt] = i;
 96                         b[cnt++] = j;
 97                     }
 98                 }
 99             }
100             cout<<cnt<<endl;
101             for(int i = 0; i < cnt; i++)
102                   cout<<"R "<<a[i]<<" "<<b[i]<<endl;
103         }
104     }
105 
106     return 0;
107 }