HDU 2819 Swap 二分匹配

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2819

题意

给定一个n*n的矩阵，问是否能够交换任意两行或两列使得主对角线上为1.能的话，给出交换方式。

思路

左边为行号，右边为列号。如果第I行第j个位1，那么左边i结点到右边j结点之间连一条边。最大匹配如果不是n那么无解。

#include<cstdio> #include<vector> #include<cstring> using namespace std; const int maxn = 110; vector<int> g[maxn]; int vis[2*maxn],match[2*maxn]; int dfs(int u) { for(int i=0,L=g[u].size(); i<L; i++) { int v=g[u][i]; if(!vis[v]) { vis[v]=1; if(match[v]==-1||dfs(match[v])) { match[v]=u; return 1; } } } return 0; } int Hungarian(int n) { int ans=0; memset(match,-1,sizeof(match)); for(int i=1; i<=n; i++) { if(match[i]==-1) { memset(vis,0,sizeof(vis)); ans+=dfs(i); } } return ans; } int main() { int n; while(~scanf("%d",&n)) { for(int i=1; i<=n; i++) g[i].clear(); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) { int t; scanf("%d",&t); if(t)g[i].push_back(j+n); } int fl=Hungarian(n); if(fl<n) printf("-1\n"); else { int L[maxn],R[maxn]; int num=0; for(int i=1; i<=n; i++) if(i!=match[i+n]) { for(int j=1; j<=n; j++) if(i==match[j+n]) { L[num]=j; R[num]=i; swap(match[i+n],match[j+n]); num++; } } printf("%d\n",num); for(int i=0;i<num;i++) printf("C %d %d\n",L[i],R[i]); } } }