*【HDU - 2819】Swap（二分图匹配，输出路径）（待证明：是否是最少交换次数？）

题干：

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

Sample Output

1
R 1 2
-1

解题报告：

看到数据量，猜到二分图。然后仔细分析二分图确实是可解的，正好二分图自带记录路径，，可能还是不是很熟练吧第一反应没有建模成二分图。左侧是行，右侧是列，然后跑二分图就可以了、题目没说求最短的变换次数，只是说一个specialjudge唯一要求是小于1000的变换次数。所以用二分图找到之后，那最多就是变换n次嘛（但是也有可能小于n次，比如第一个样例，就直接换了一次凑出俩来，严谨来讲(n/2)<=cnt<=n），n<=100，所以肯定满足题意啊。如果说求最少的变换次数，那就应该先把(ans[i]== j && ans[j] == i)的找出来，然后再遍历剩下的？（但是感觉好像和直接遍历的次数差不多啊。。但是不太会证明、、）

AC代码：（140ms）

#include<bits/stdc++.h>

using namespace std;
const int MAX = 100 + 5;
bool used[MAX];
int line[MAX][MAX],nxt[MAX],ans[MAX],n,cnt;
bool find(int x) {
	for(int i = 1; i<=n; i++) {
		if(line[x][i] && used[i] == 0) {
			used[i]=1;
			if(nxt[i] == 0 || find(nxt[i])) {
				nxt[i] = x;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	while(~scanf("%d",&n)) {
		cnt = 0;
		memset(line,0,sizeof line);
		memset(ans,0,sizeof ans);
		memset(nxt,0,sizeof nxt);
		for(int i = 1; i<=n; i++) {
			for(int j = 1; j<=n; j++) {
				scanf("%d",&line[i][j]);
			}
		}
		for(int i = 1; i<=n; i++) {
			memset(used,0,sizeof used);
			if(find(i)) cnt++;
		}
		if(cnt != n) {
			puts("-1");continue;
		}
		cnt = 0;
		for(int i = 1; i<=n; i++) {
			ans[nxt[i]] = i;//ans[i] = j   第i列应该等于第j列 //或者说 第i行换到第j行 
		}
		for(int i = 1; i<=n; i++) {
			if(ans[i] != i) {//如果这行需要换
				for(int j = i+1; j<=n; j++) {
					if(ans[j] == i) {
						swap(ans[i],ans[j]);cnt++;
					}
				}
				
			}
		}
		printf("%d\n",cnt);
		for(int i = 1; i<=n; i++) {
			ans[nxt[i]] = i;//ans[行] = 列 
		}
		for(int i = 1; i<=n; i++) {
			if(ans[i] != i) {
				for(int j = i+1; j<=n; j++) {
					if(ans[j] == i) {
						printf("R %d %d\n",i,j);
						swap(ans[i],ans[j]);
					}
				}
				
			}
		}
	} 
	return 0 ;
 }

总结：

       for(int i = 1; i<=n; i++) {
           ans[nxt[i]] = i;//ans[行] = 列
       }

这一行作用是：ans[i]=j，表示第i行应该换到第j行。（你如果最后输出是C的，也就是换列的，那就不需要这个转换了）

还有一点值得注意，我们的思路不是如果第i行需要换(即ans[i]=j)，则把i和j交换，并且用一个bk数组标记第j行已经完成，再从1找第一个bk=0的行，然后再进行交换。（这样会使代码写起来复杂。而且每次都得从i=1开始找，因为有可能ans[i]=j其中j<i？不知道会不会有这种可能性）（但是时间复杂度是不会变的，因为每次都会有一个行被确定下来）

当然，也可以AC，下面是部分代码：（140ms）

		for(int i = 1; i<=n; i++) {
			ans[nxt[i]] = i;//ans[行] = 列 
		}
		int flag = 0;
		while(1) {
			flag = 0;
			for(int i = 1; i<=n; i++) {
				if(ans[i] != i) {
					flag = 1;
					int j = ans[i];
					printf("R %d %d\n",i,j);
					swap(ans[i],ans[j]);
					break;
				}
			}			
			if(flag == 0) break;
		}

但是，我们不妨换个思路，扫到这行i之后，然后现在我们的想法是要把这样固定下来，也就是，从后面的行中找到一行假设为j，使得ans[j] = i ，也就是用第j行来确定第i行，然后这两行交换，这样一个for循环扫每一行就可以了，扫到一行，就从后面的行中找一行来确定这一行。就ok了。至于为什么从i+1行开始，是因为第1~(i-1)行，都已经是ans[i]=i了呀，这也就是这两个方法的不同。（前者是找到一个可以更新别的行的行，然后去更新后面的行；后者是枚举每一行，然后从后面找一行来更新这一行。不过代码实现起来都是if(ans[i] != i)这一句）