HDU - 2819 Swap(二分图最大匹配)

时间:2023-12-18 20:43:02
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?

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的棋盘,值都是0或1,你可以任意交换两行两列,不要求最少步数,交换的结果让对角线都为1 思路:首先我们可以看出如果可以交换出结果,只依靠行交换或者列交换即可,然后我们要求的是一条对角线,意思是每列匹配的位置必须是固定的行,
我们把行当做二分图的左边,列当做二分图的右边,1的时候就是行和列直接有一条边,
-1问题我们直接用匈牙利算法求出,求出最大匹配是否是n,如果不是的话,说明有些行还没有匹配,所以不符合要求,如果最大匹配是n的话
我们可以去找属于自己的列,如图

HDU - 2819   Swap(二分图最大匹配)

说明满足第一行的匹配在第二列,但是我现在匹配的是第三列,这个时候就要把这两列交换一下,得到以下结果

HDU - 2819   Swap(二分图最大匹配)

这个时候第二行匹配错了,所以2,3行交换,然后得到的结果就匹配完成了

HDU - 2819   Swap(二分图最大匹配)

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
struct sss
{
int x,y;
}a[];
int n;
int mp[][];
int vis[];
int girl[];
int dfs(int x)
{
for(int i=;i<=n;i++)
{
if(mp[x][i]&&vis[i]==)
{
vis[i]=;
if(girl[i]==||dfs(girl[i]))
{
girl[i]=x;
return ;
}
}
}
return ;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(girl,,sizeof(girl));
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
scanf("%d",&mp[i][j]);
}
int sum=;
for(int i=;i<=n;i++)
{
memset(vis,,sizeof(vis));
sum+=dfs(i);
}
if(sum!=n) printf("-1\n");//看是否满足全部匹配到了
else{
int num=;
for(int i=;i<=n;i++)
{
if(i!=girl[i])//灵活利用girl数组记录了匹配的行
{
for(int j=i+;j<=n;j++)//如果当前行匹配出错,找出需要匹配的行在哪里
{
if(i==girl[j])
{
int t;
t=girl[i];
girl[i]=girl[j];
girl[j]=t;
a[num].x=i;
a[num].y=j;
num++;
break;
}
}
}
}
printf("%d\n",num);
for(int i=;i<num;i++)
{
printf("C %d %d\n",a[i].x,a[i].y);
}
}
}
}