题目大意：
给定一个元素的值只有1或者0的矩阵，每次可以交换两行（列），问有没有方案使得对角线上的值都是1。题目没有限制需要交换多少次，也没限制行交换或者列交换，也没限制是主对角线还是副对角线。虽然没限制，但是解法都是差不多的。
这是09年的多校题目，对一般人来说，不看解题报告是无法做出来的。我是那种看了解题报告也没做出来，然后看了好几遍才看懂的人。
http://www.cnblogs.com/jzlikewei/archive/2012/07/09/2583608.html
解题思路：
对于二分图模型｛X，Y| E｝，我们可以把行作为X集合里的点，把列作为Y集合里的点，边就是值为满足MAP[x][y]=1的条件。判断有没有解就是判断所有的行有没有匹配，也就是最大匹配是否等于n。
按照顺序输出交换的行(或者是列)是通过而一个二重循环。比如说：从第一行开始，如果它与匹配的列不相等（对角线需要行列相等），就从第二行开始找，直到找到匹配的列等于1。然后把此行匹配的列改为第一行匹配的列。一直下去。因为没有要求最小交换次数的解，所以这样暴力求解就可以了。
在一般的求最大匹配的模版中，都会有数组cx[],cx[]。其中cx[]记录与X集合匹配的Y集合中元素的标号，cy[]是记录与Y集合匹配的X集合中元素的标号。比如说,cx[3]=2的意思是与X集合中3号元素匹配的Y的集合的元素的编号是2。这两个数组一般情况下只要一个就够的，有些题目就需要输出匹配的序列。
下面的我的代码：Hopcroft-Karp算法，代码有点长，时间复杂度低。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=,INF=0x3f3f3f3f;
int cx[N],cy[N],dx[N],dy[N],bmap[N][N];
bool bmask[N];
int nx,ny,dis,ans;
bool searchpath()
{
queue<int> q;
dis=INF;
memset(dx,-,sizeof(dx));
memset(dy,-,sizeof(dy));
for(int i=;i<=nx;i++)
{
if(cx[i]==-){ q.push(i); dx[i]=; }
while(!q.empty())
{
int u=q.front(); q.pop();
if(dx[u]>dis) break;
for(int v=;v<=ny;v++)
{
if(bmap[u][v]&&dy[v]==-)
{
dy[v]= dx[u] + ;
if(cy[v]==-) dis=dy[v];
else
{
dx[cy[v]]= dy[v]+;
q.push(cy[v]);
}
}
}
}
}
return dis!=INF;
}
int findpath(int u)
{
for(int v=;v<=ny;v++)
{
if(!bmask[v]&&bmap[u][v]&&dy[v]==dx[u]+)
{
bmask[v]=;
if(cy[v]!=-&&dy[v]==dis) continue;
if(cy[v]==-||findpath(cy[v]))
{
cy[v]=u; cx[u]=v;
return ;
}
}
}
return ;
}
void maxmatch()
{
ans=;
memset(cx,-,sizeof(cx));
memset(cy,-,sizeof(cy));
while(searchpath())
{
memset(bmask,,sizeof(bmask));
for(int i=;i<=nx;i++)
if(cx[i]==-) ans+=findpath(i);
}
}
struct node
{
int x,y;
}e[N];
int main()
{
//freopen("test.txt","r",stdin);
int cas,i,j,k,n;
while(scanf("%d",&n)!=EOF)
{
for(i=;i<=n;i++)
for(j=;j<=n;j++)
scanf("%d",&bmap[i][j]);
nx=ny=n;
maxmatch();
if(ans<n) {printf("-1\n");continue;}
k=;
for(i=;i<=n;i++){
if(cx[i]!=i){
for(int j=i+;j<=n;j++){
if(cx[j]==i){
e[k].x=i;e[k++].y=j;
cx[j]=cx[i];
break;
}
}
}
}
printf("%d\n",k);
for(i=;i<k;i++)
printf("R %d %d\n",e[i].x,e[i].y);
}
return ;
}