FMATCH - Fast Maximum Matching

Tác giả: skyvn97

Ngôn ngữ: C++

#include<cstdio>
#include<vector>
#include<queue>
#define MAX   50505
using namespace std;
const int INF=(int)1e7;
vector<int> g[MAX];
int matx[MAX];
int maty[MAX];
int d[MAX];
int m,n,p;
void loadgraph(void) {
	scanf("%d",&m);
	scanf("%d",&n);
	scanf("%d",&p);
	int i,u,v;
	for (i=1;i<=p;i=i+1) {
		scanf("%d",&u);
		scanf("%d",&v);
		g[u].push_back(v);
	}
}
bool BFS(void) {
	queue<int> q;
	while (!q.empty()) q.pop();
	int i,u,v;
	for (i=1;i<=m;i=i+1) {
		if (matx[i]==0) {
			d[i]=0;
			q.push(i);
		}
		else d[i]=INF;
	}
	d[0]=INF;
	while (!q.empty()) {
		u=q.front();q.pop();
		if (d[u]<d[0])
			for (i=0;i<g[u].size();i=i+1) {
				v=g[u][i];
				if (d[maty[v]]>=INF) {
					d[maty[v]]=d[u]+1;
					q.push(maty[v]);
				}
			}
	}
	return (d[0]<INF);
}
bool DFS(const int &u) {
	if (u==0) return (true);
	int i,v;
	for (i=0;i<g[u].size();i=i+1) {
		v=g[u][i];
		if (d[maty[v]]==d[u]+1)
			if (DFS(maty[v])) {
				matx[u]=v;
				maty[v]=u;
				return (true);
			}		
	}
	d[u]=INF;
	return (false);
}
void fastmatching(void) {
	int i;
	for (i=1;i<=m;i=i+1) matx[i]=0;
	for (i=1;i<=n;i=i+1) maty[i]=0;
	int res=0;
	while (BFS()) {
	//	printf("ok\n");
		for (i=1;i<=m;i=i+1)
			if (matx[i]==0)
				if (DFS(i)) res++;
		//printf("%d\n",res);
	}
	printf("%d",res);
}
int main(void) {
#ifndef ONLINE_JUDGE
	freopen("tmp.txt","r",stdin);
#endif
	loadgraph();
	fastmatching();
	return 0;
}

Download