2 0 1 1 0 2 1 0 1 0
1 R 1 2 -1
#include<stdio.h>
#include<string.h>
int map[1010][1010],r[1010][1010],link[1010],vis[1010],n,row1[1010],row2[1010];
int dfs(int u)
{
int i;
for(i=1;i<=n;i++)
{
if(map[u][i]&&!vis[i])
{
vis[i]=1;
if(link[i]==-1||dfs(link[i]))
{
link[i]=u;
return 1;
}
}
}
return 0;
}
int main()
{
//int n;
while(scanf("%d",&n)!=EOF)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
scanf("%d",&map[i][j]);
}
memset(link,-1,sizeof(link));
memset(r,0,sizeof(r));
for(i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(!dfs(i))
break;
}
if(i<=n)
printf("-1\n");
else
{
int k=0;
for(i=1;i<=n;i++)
{
if(r[i][link[i]]==0&&i!=link[i])
{
k++;
r[i][link[i]]=r[link[i]][i]=1;
if(i<link[i])
{
row1[k]=i;
row2[k]=link[i];
}
else
{
row1[k]=link[i];
row2[k]=i;
}
for(j=i+1;j<=n;j++)
{
if(link[j]==i)
{
link[j]=link[i];
break;
}
}
}
}
printf("%d\n",k);
for(i=1;i<=k;i++)
{
printf("R %d %d\n",row1[i],row2[i]);
}
}
}
}HDOJ 题目2189 Swap(二分图最大匹配,输出路径)
原文:http://blog.csdn.net/yu_ch_sh/article/details/44628741