HDU2819-Swap-二分图匹配

把矩阵上的1建成边,把边建成点

然后跑一个二分图匹配,就找到了主对角线的元素,之后排个序就可以了

 /*--------------------------------------------------------------------------------------*/

 #include <algorithm>
#include <iostream>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map> //debug function for a N*M array
#define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++)\
{for(int j=;j<(M);j++){\
printf("%d",G[i][j]);}printf("\n");}
//debug function for int,float,double,etc.
#define debug_var(X) cout<<#X"="<<X<<endl;
#define LL long long
const int INF = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
/*--------------------------------------------------------------------------------------*/
using namespace std; int N,M,T;
const int maxn = ;
const int maxm = ; struct Edge{
int to,next;
}edge[maxm];
int head[maxn],tot;
void init()
{
tot = ;
memset(head,-,sizeof head);
}
void add_edge(int u,int v)
{
edge[tot].to = v;edge[tot].next = head[u];
head[u] = tot++;
} int linker[maxn];
bool used[maxn];
int uN; bool dfs(int u)
{
for(int i=head[u];~i;i =edge[i].next)
{
int v = edge[i].to;
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<=uN;u++)
{
memset(used,false,sizeof used);
if(dfs(u)) res++;
}
return res/;
}
vector <pair<int,int> > op;
int save[maxn]; bool ok()
{
for(int i=;i<=N;i++) if(save[i] != i) return false;
return true;
} int main()
{
while(~scanf("%d",&N))
{
uN = *N;
init();
for(int i=;i<=N;i++)
{
for(int j=,tmp;j<=N;j++)
{
scanf("%d",&tmp);
if(tmp == )
{
add_edge(i,j+N);
add_edge(j+N,i);
}
}
}
int match = hungary();
if(match < N)
{
printf("-1\n");
}
else
{
for(int u=;u<=N;u++)
{
int v = linker[u] - N;
//printf("[%d,%d]\n",u,v);
save[u] = v;
}
op.clear();
while(!ok())
{
for(int i=;i<=N;i++)
{
if(save[i] != i)
{
op.push_back(make_pair(i,save[i]));
swap(save[i],save[save[i]]);
}
}
}
printf("%d\n",op.size());
for(int i=;i<op.size();i++)
{
printf("R %d %d\n",op[i].first,op[i].second);
}
}
}
}
上一篇:VMware Workstation 9.0 安装苹果Mac OS X10.9系统


下一篇:Logstash学习-配置语法