# 【匈牙利算法】

## 实战

### [hdu2063]过山车

``````#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1000+5,M=500+5,inf=0x3f3f3f3f,P=19650827;
int k,n,m,ans,match[N];
template <class t>void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}

bool dfs(int x){
for(int i=1;i<=n;++i){//扫描每个男生
vis[i]=1;
if(!match[i]||dfs(match[i])){match[i]=x;return 1;}
//名花无主或者能腾出空位置来
}
}
return 0;
}

int main(){
while(scanf("%d",&k)!=EOF&&k){
ans=0;
memset(match,0,sizeof(match));
rd(m),rd(n);
for(int i=1;i<=m;++i){
memset(vis,0,sizeof(vis));
if(dfs(i)) ++ans;
}
printf("%d\n",ans);
}
return 0;
}``````
dfs版
```>```queue Q;
int prev[__maxNodes];
int Hungarian()
{
int ans = 0;
memset(matching, -1, sizeof(matching));
memset(check, -1, sizeof(check));
for (int i=0; i= 0) { // 此点为匹配点
prev[matching[v]] = u;
} else { // 找到未匹配点，即找到增广路
flag = true;
int d=u, e=v;
while (d != -1) {//修改原来的匹配关系
int t = matching[d];
matching[d] = e;
matching[e] = d;
d = prev[d];
e = t;
}
}
}
}
Q.pop();
}
if (matching[i] != -1) ++ans;
}
}
return ans;
}``````

### [SCOI2010]游戏

(还可以用并查集做 具体看黄学长der

vis太大用memset会超时 从标程上学到 用一个数组gai记录变了的vis 然后初始化时只改变了的

``````#include<bits/stdc++.h>
using namespace std
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))
const int N=1000000+5,M=10000+5,inf=0x3f3f3f3f,P=19650827;
int n,mx,ans,match[N],gai[N];
double vis[N];
template <class t>void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}

struct edge{int v,nxt;}e[N<<1];
void add(int u,int v){
}

bool dfs(int x){
if(!vis[v=e[i].v]){
vis[gai[++gai[0]]=v]=1;
if(!match[v]||dfs(match[v])){match[v]=x;return 1;}
}
return 0;
}

int main(){
freopen("in2.txt","r",stdin);
//freopen("xor.out","w",stdout);
rd(n);mx=ans=0;
for(int i=1;i<=mx;++i){
for(int i=1;i<=gai[0];++i) vis[gai[i]]=0;gai[0]=0;
if(dfs(i)) ++ans;
else break;
}
printf("%d",ans);
return 0;
}``````

### luogu1402酒店之王

(fromluogu讨论区

`3 2 2 1 1 1 2 1 1 1 1 1 1 2 1`

`2`

`3 2 2 1 1 1 1 1 1 1 2 1 1 2 1`

`2`

``````#include<bits/stdc++.h>
using namespace std;
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))
const int N=100+5,M=10000+5,inf=0x3f3f3f3f,P=19650827;
int n,p,q,ans,match1[N],match2[N],M1[N],M2[N];
bool vis[N],vis2[N],lka[N][N],lkb[N][N];
template <class t>void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}

bool dfs1(int x){
for(int i=1;i<=p;++i)
if(lka[x][i]&&!vis[i]){
vis[i]=1;
if(!match1[i]||dfs1(match1[i])){match1[i]=x;return 1;}
}
return 0;
}
bool dfs2(int x){
for(int i=1;i<=q;++i)
if(lkb[x][i]&&!vis2[i]){
vis2[i]=1;
if(!match2[i]||dfs2(match2[i])){match2[i]=x;return 1;}
}
return 0;
}

int main(){
//freopen("in2.txt","r",stdin);
//freopen("xor.out","w",stdout);
ans=0;
rd(n),rd(p),rd(q);
for(int i=1;i<=n;++i)
for(int j=1;j<=p;++j) rd(lka[i][j]);
for(int i=1;i<=n;++i)
for(int j=1;j<=q;++j) rd(lkb[i][j]);
for(int i=1;i<=n;++i){
memset(vis,0,sizeof(vis));
memset(vis2,0,sizeof(vis2));
for(int i=1;i<=p;++i) M1[i]=match1[i];
for(int i=1;i<=q;++i) M2[i]=match2[i];
if(dfs1(i)&&dfs2(i)) ++ans;
else{
for(int i=1;i<=p;++i) match1[i]=M1[i];
for(int i=1;i<=q;++i) match2[i]=M2[i];
}
}
printf("%d",ans);
return 0;
}``````

### [SCOI2001]小狗散步

luogu2526

``````#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))
const int N=100+5,M=10000+5,inf=0x3f3f3f3f,P=19650827;
int n,m,ans=0,match[N];
bool vis[N],lnk[N][N];
template <class t>void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}

struct node {
int x,y;
}a[N],b[N];
double qdis(node A,node B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}

bool dfs(int x){
for(int i=1;i<=n;++i)
if(lnk[x][i]&&!vis[i]){
vis[i]=1;
if(!match[i]||dfs(match[i])){match[i]=x;return 1;}
}
return 0;
}

int main(){
freopen("in2.txt","r",stdin);
//freopen("xor.out","w",stdout);
rd(n),rd(m);
for(int i=1;i<=n;++i) rd(a[i].x),rd(a[i].y);
for(int i=1;i<=m;++i) rd(b[i].x),rd(b[i].y);
for(int i=1;i<n;++i)
for(int j=1;j<=m;++j)
if(qdis(a[i],a[i+1])*2.0>=qdis(a[i],b[j])+qdis(b[j],a[i+1])) lnk[j][i]=1;
for(int i=1;i<=m;++i){
memset(vis,0,sizeof(vis));
if(dfs(i)) ++ans;
}
printf("%d\n",ans+n);
for(int i=1;i<n;++i){
printf("%d %d ",a[i].x,a[i].y);
if(match[i]) printf("%d %d ",b[match[i]].x,b[match[i]].y);
}
printf("%d %d",a[n].x,a[n].y);
return 0;
}``````

【匈牙利算法】

(0)
(0)

© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4