HDU - 2819 Swap (二分图匹配-匈牙利算法)

题意:一个N*N的01矩阵,行与行、列与列之间可以互换。要求变换出一个对角线元素全为1的矩阵,给出互换的行号或列号。

分析:首先一个矩阵若能构成对角线元素全为1,那么矩阵的秩为N,秩小于N的情况无解。所以一个矩阵可以仅通过行变换不能得到最后结果,那么仅通过列变换或者行列变换都不能得到。

可以将行号看作二分图的X部,列号对应二分图Y部,那么矩阵Mij为1就可以视作第i行可以与第j列相匹配。而构成对角线全1的情况就是行与列之间有N对匹配关系,若小于N则无解。

根据所给的矩阵建二分图跑匈牙利,然后可以得到二分图Y部的匹配数组linker。linker[j]记录的便是第j列应该与第linker[j]行相匹配;换言之,第j列应该与第linker[j]列互换。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
const int maxn =;
const int INF =0x3f3f3f3f; int N;
int G[maxn][maxn];
int linker[maxn];
bool used[maxn]; void init(){memset(G,,sizeof(G));} bool dfs(int u){
for(int v=;v<=N;++v){
if(!G[u][v]) continue;
if(!used[v]){
used[v]=true;
if(linker[v]==- || dfs(linker[v])){
linker[v]=u;
return true;
}
}
}
return false;
} int hungary(){
int res=;
memset(linker,-,sizeof(linker));
for(int u=;u<=N;u++){
memset(used,,sizeof(used));
if(dfs(u)) res++;
}
return res;
} int L[maxn],R[maxn]; #define LOCAL
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int T,M,u,v,tmp,K,cas=;
while(scanf("%d",&N)==){
init();
for(int i=;i<=N;++i){
for(int j=;j<=N;++j){
scanf("%d",&G[i][j]);
}
}
int ans = hungary();
if(ans<N){
printf("-1\n");
continue;
}
int res=;
for(int i=;i<=N;++i){
for(int j=;j<=N;++j){
if(j==i) continue;
if(linker[j]==i){
L[res] = i,R[res++]=j;
swap(linker[j],linker[i]);
break;
}
}
}
printf("%d\n",res);
for(int i=;i<res;++i)
printf("C %d %d\n",L[i],R[i]);
}
return ;
}
上一篇:网易2019校招内推编程题-俄罗斯方块-C++实现


下一篇:解决谷歌浏览器中的input背景色默认是黄色