【模板】解决二分图匹配的强力算法—

详细解释

参见：http://blog.csdn.net/wall_f/article/details/8248373

简要过程

HK算法可以当成是匈牙利算法的优化版，和dinic算法的思想比较类似。

每次先通过bfs来确定所有点的距离，然后再对每个点进行dfs找增广路，并限制每次增广的时候（走到的点的距离）=（当前的点距离+1）。

于是很愉快地在UOJ跑进了第一页~

upd:加了一些特技之后跑的更快了

模板代码

//UOJ 78

#include <bits/stdc++.h>

using namespace std;

const int MAXN=505, MAXB=2e7, INF=0x3f3f3f3f;

char buf[MAXB], *cp=buf;

void rd(int &x){

	x=0;

	while(*cp<'0'||'9'<*cp) cp++;

	while('0'<=*cp&&*cp<='9') x=x*10+*cp-'0', cp++;

}

int nl, nr, M, now, dis;

int ml[MAXN], mr[MAXN], dl[MAXN], dr[MAXN], vis[MAXN], q[MAXN];

int E[MAXN][MAXN], sz[MAXN];

int bfs(){

	memset(dl, -1, sizeof(dl));

	memset(dr, -1, sizeof(dr));

	int ff=0, rr=0; dis=INF;

	for(int i=1; i<=nl; ++i) if(!ml[i]) dl[i]=0, q[rr++]=i;

	while(ff<rr){

		int u=q[ff++]; if(dl[u]>dis) break;

		for(int *e=E[u]; *e; ++e){

			int v=*e;

			if(dr[v]==-1){

				dr[v]=dl[u]+1;

				if(mr[v]){dl[mr[v]]=dr[v]+1, q[rr++]=mr[v];}

				else dis=dr[v];

			}

		}

	}

	return dis<INF;

}

int dfs(int u){

	for(int *e=E[u]; *e; ++e){

		int v=*e;

		if(dr[v]==dl[u]+1&&vis[v]!=now){

			vis[v]=now;

			if(!mr[v]||dfs(mr[v])) return mr[v]=u, ml[u]=v, 1;

		}

	}

	return 0;

}

int HK(){

	int r=0;

	while(bfs()){

		now++;

		for(int i=1; i<=nl; ++i) if(!ml[i]) r+=dfs(i);

	}return r;

}

int main(){

	fread(buf, 1, MAXB, stdin);

	rd(nl), rd(nr), rd(M);

	for(int i=0, u, v; i<M; ++i) rd(u), rd(v), E[u][sz[u]++]=v;

	printf("%d\n", HK());

	for(int i=1; i<nl; ++i) printf("%d ", ml[i]);

	printf("%d\n", ml[nl]);

	return 0;

}

巴特西

【模板】解决二分图匹配的强力算法——Hopcroft-Karp算法

详细解释

简要过程

模板代码

最新文章

热门文章