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