题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=2819
题目大意：给你一个n*n的01矩阵，问是否可以通过任意交换整行或者整列使得正对角线上都是1。
解题思路：
按行列建图，求最大匹配，若最大匹配数<n，则肯定无解（矩阵的秩要等于n才有解）。
若有解，则肯定可以通过只交换行或者交换列得到。所以我们从i=1 to n检查link[i]=i（link[i]表示第i列的1对应的行号）是否成立，
否则找到link[j]=i交换link[i]和link[j]并记录下交换步骤。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e3+; int n;
int link[N];
bool vis[N];
vector<int>v[N];
struct node{
int x,y;
node(int x,int y):x(x),y(y){}
}; bool dfs(int u){
for(int i=;i<v[u].size();i++){
int t=v[u][i];
if(!vis[t]){
vis[t]=true;
if(link[t]==-||dfs(link[t])){
link[t]=u;
return true;
}
}
}
return false;
} int max_match(){
memset(link,-,sizeof(link));
int ans=;
for(int i=;i<=n;i++){
memset(vis,false,sizeof(vis));
if(dfs(i)) ans++;
}
return ans;
} int main(){
while(~scanf("%d",&n)){
for(int i=;i<=n;i++) v[i].clear();
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
int x;
scanf("%d",&x);
if(x) v[i].push_back(j);
}
}
if(max_match()<n)
puts("-1");
else{
vector<node>ans;
for(int i=;i<=n;i++){
//若link[i]!=i则找到对应的link[j]==i与之交换，满足link[i]=i
if(link[i]!=i){
for(int j=;j<=n;j++){
if(link[j]==i){
swap(link[i],link[j]);
ans.push_back(node(i,j));
}
}
}
}
printf("%d\n",ans.size());
for(int i=;i<ans.size();i++){
printf("C %d %d\n",ans[i].x,ans[i].y);
}
}
}
return ;
}