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;
}