FMATCH - Fast Maximum Matching

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include <cstdio>
#include <cstring>
using namespace std;

struct List {
	int i;
	List * next;	
};

List cont[400000];
int ncont1, ncont2;

List * ke[50050];
List * keY[50050];

int M, N, nE;
int X[50050], Y[50050], Q[50050], levelX[50050], levelY[50050];
bool vs[50050];
int L, R, maxLevel, socap;

inline void addList( List * & p, int i, int & cn) {
	List * q = cont + ++cn;
	q->i = i;
	q->next = p;
	p = q;
}

bool bfs() {
	L = 1;
	R = 0;
	memset( levelX, 0, sizeof(levelX));
	memset( levelY, 0, sizeof(levelY));
	ncont2 = 155000;
	memset( keY, 0, sizeof(keY));
	
	for(int i=1;i<=M;++i) if(X[i]==0) Q[++R] = i, levelX[i] = 1;
	maxLevel = 1000000;
	while(L<=R) {
		int u = Q[L++];
		if(levelX[u] > maxLevel) break;
		for(List * p = ke[u]; p!=NULL; p = p->next) {
			int v = p->i;
			if(levelY[v]==0) {
				levelY[v] = levelX[u] + 1;
				if(Y[v]==0)
					maxLevel = levelY[v];
				else 
					if(levelX[Y[v]]==0) {
						levelX[Y[v]] = levelY[v] + 1;
						Q[++R] = Y[v];
					}
			}
			if(levelY[v] == levelX[u] + 1) addList( keY[v], u, ncont2);
		}
	}
	return maxLevel < 1000000;
}

bool dfs(int j) {
	for(List * p = keY[j]; p!=NULL; p = p->next) {
		int i = p->i;
		if(!vs[i]) {
			vs[i] = true;
			if(levelX[i]==1 || dfs(X[i])) {
				X[i] = j;
				Y[j] = i;
				return true;
			}
		}
	}
	return false;
}

void tang() {
	memset( vs, 0, sizeof(vs));
	for(int i=1;i<=N;++i) 
		if(levelY[i]==maxLevel && Y[i]==0)
			if(dfs(i)) ++socap;
}

int main() {
	scanf("%d%d%d", &M, &N, &nE);
	for(int i=0;i<nE;++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		if(X[u]==0 && Y[v]==0) {
			X[u] = v;
			Y[v] = u;
			++socap;
		}
		addList( ke[u], v, ncont1);
	}	
	while(bfs()) tang();
	printf("%d\n", socap);
	return 0;
}

Download