HDU 2819 矩阵交换列使得主对角线都为1 二分匹配

给定矩阵，通过行变换或列变换使得主对角线元素都为1

对于矩阵，只需要 只使用列变换 或 只使用行变换 操作即可得到结果

输出列变换的 哪2列进行交换，按字典序

#include<stdio.h>#include<string.h>#include<algorithm>#include<vector>#define N 206using namespace std;int n;int lef[N], pn;//lef[v]表示Y集的点v 当前连接的点  bool T[N];     //T[u] 表示Y集 u 是否已连接X集vector<int>G[N]; //匹配边  G[X集].push_back(Y集)  注意G 初始化bool match(int x){ // x和Y集 匹配 返回x点是否匹配成功for(int i=0; i<G[x].size(); i++){int v = G[x][i];if(!T[v]){T[v] = true;if(lef[v] == -1 || match( lef[v] ))   //match(lef[v]) : 原本连接v的X集点 lef[v] 能不能和别人连，如果能 则v这个点就空出来和x连{lef[v] = x;return true;}}}return false;}int solve(){int ans = 0;memset(lef, -1, sizeof(lef));for(int i = 1; i<= pn; i++)//X集匹配，X集点标号从 1-pn 匹配边是G[左点].size()   {memset(T, 0, sizeof(T));if( match( i ) ) ans++;}return ans;}int map[N][N],a[1010],b[1010];int main(){int i,j;while(~scanf("%d",&n)){for(i=0;i<=n;i++)G[i].clear();for(i=1;i<=n;i++)for(j=1;j<=n;j++){scanf("%d",&map[i][j]);if(map[i][j])G[i].push_back(j);}pn = n;int ans=solve();if(ans<n){printf("-1\n");continue;}int res=0;for(i=1;i<=n;i++){for(j=i;j<=n;j++)//对于i列 找到j列是和i列交换才满足条件的if(lef[j] == i)break;if(j!=i)//一样就是对应位置已经为1 不需要交换了{a[res] = i; b[res++] = j;int t = lef[i]; lef[i] = lef[j]; lef[j] = t;//去重}}printf("%d\n",res);for(i=0;i<res;i++)printf("C %d %d\n",a[i],b[i]);}return 0;}/*20 11 021 01 0*/