题目链接：https://cn.vjudge.net/problem/HDU-2819
InputThere 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.OutputFor 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
题意：
给出一个N*N的01矩阵，要求你通过一些行交换或者列交换使得矩阵的主对角线上全为1；
题解：
不难想象，进行行列缩点，如果某个位置aij等于1，就往二分图中加入一条边( i , j )，如果求出最大匹配等于N，说明可以通过行列的变换得到目标矩阵；
然后根据匹配情况，输出相应的交换步骤即可；
AC代码：
#include<bits/stdc++.h>
#define MAX 103
#define INF 0x3f3f3f3f
using namespace std;
int n,matrix[MAX][MAX]; struct Hopcroft_Karp{
int edge[MAX][MAX],Mx[MAX],My[MAX],Nx,Ny;
int dx[MAX],dy[MAX],dis;
bool vis[MAX];
void init(int uN,int vN)
{
Nx=uN, Ny=vN;
for(int i=;i<=uN;i++) for(int j=;j<=vN;j++) edge[i][j]=;
}
void addedge(int u,int v){edge[u][v]=;}
bool searchP()
{
queue<int> Q;
dis=INF;
memset(dx,-,sizeof(dx));
memset(dy,-,sizeof(dy));
for(int i=;i<=Nx;i++)
{
if(Mx[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(edge[u][v] && dy[v]==-)
{
dy[v]=dx[u]+;
if(My[v]==-) dis=dy[v];
else
{
dx[My[v]]=dy[v]+;
Q.push(My[v]);
}
}
}
}
return dis!=INF;
}
bool dfs(int u)
{
for(int v=;v<=Ny;v++)
{
if(!vis[v] && edge[u][v] && dy[v]==dx[u]+)
{
vis[v]=;
if(My[v]!=- && dy[v]==dis) continue;
if(My[v]==- || dfs(My[v]))
{
My[v]=u;
Mx[u]=v;
return true;
}
}
}
return false;
}
int max_match()
{
int ret=;
memset(Mx,-,sizeof(Mx));
memset(My,-,sizeof(My));
while(searchP())
{
memset(vis,,sizeof(vis));
for(int i=;i<=Nx;i++) if(Mx[i]==- && dfs(i)) ret++;
}
return ret;
}
}HK; int main()
{
while(scanf("%d",&n)!=EOF)
{
HK.init(n,n);
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
scanf("%d",&matrix[i][j]);
if(matrix[i][j]) HK.addedge(i,j);
}
} int max_match=HK.max_match();
if(max_match==n)
{
queue< pair<int,int> > output;
for(int j=;j<=n;j++)
{
int u1=j, u2=HK.My[j];
int v1=j, v2=HK.Mx[j];
if(u1!=u2)
{
output.push(make_pair(u1,u2));
HK.My[v1]=u1, HK.My[v2]=u2;
HK.Mx[u1]=v1, HK.Mx[u2]=v2;
}
} printf("%d\n",output.size());
while(!output.empty())
{
printf("R %d %d\n",output.front().first,output.front().second);
swap(matrix[output.front().first],matrix[output.front().second]);
output.pop();
}
}
else printf("-1\n");
}
}
PS.刚开始还以为HK算法的模板出错了，吓死了……
PS.注意更改匹配情况时，match数组的变更；