本文主要是介绍hdu2819 Swap，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给行列均为n的由0和1构成的矩阵，
求一种方案，每次交换两行或两列，使得最后从左上到右下的对角线上全部为1，没有方案则输出0.
首先用二分图最大匹配求可行解。
主要是输出比较麻烦，我是每次循环交换一次，保证有一个已经换到的对的位置，最多n次一定能把所有行列换到正确位置。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#pragma comment(linker, "/STACK:16777216")
#define eps 1e-6
#define ll long long
using namespace std;int n,mx[110],my[110],vis[110],e[110][110];int path(int i)
{int j;for(j=1;j<=n;j++){if(e[i][j]&&!vis[j]){vis[j]=1;if(my[j]==-1||path(my[j])){my[j]=i;mx[i]=j;return 1;}}}return 0;
}int hungary()
{int res=0;memset(mx,-1,sizeof mx);memset(my,-1,sizeof my);for(int i=1;i<=n;i++){if(mx[i]==-1){memset(vis,0,sizeof vis);res+=path(i);}}return res;
}int main()
{int i,j;while(~scanf("%d",&n)){for(i=1;i<=n;i++){for(j=1;j<=n;j++)scanf("%d",&e[i][j]);}int ans=hungary();if(ans!=n) printf("-1\n");else{int p[110][2],flag=1;ans=0;memset(vis,0,sizeof vis);for(i=1;i<=n;i++){flag=0;// printf("i:%d mxi:%d\n",i,mx[i]);if(!vis[i]&&mx[i]!=i){flag=1;p[ans][0]=i;p[ans++][1]=mx[i];vis[mx[i]]=1;mx[i]=mx[mx[i]];i=1;}if(i==n&&!flag) break;}printf("%d\n",ans);for(i=0;i<ans;i++)printf("R %d %d\n",p[i][0],p[i][1]);}}return 0;
}/*
4
0 1 0 0
0 0 1 0
0 0 0 1
1 0 1 1
*/
这篇关于hdu2819 Swap的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
