SPOJ 4206二分整合HKアルゴリズム
2764 ワード
テンプレート問題の順方向星建辺のHKアルゴリズム
#include <iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
using namespace std;
const int maxn=50100;
const int maxm=151000;
const int INF=0x3f3f3f3f;
struct EDGE
{
int b;
int next;
};
int nx, ny, m;
EDGE edge[maxm];
int edge_num;
int first[maxn];
int cx[maxn],cy[maxn];// cx[i] xi ,cy[i] yi .
int distx[maxn],disty[maxn]; // , BFS .
int que[maxn*10];
int ans;
inline void Init()
{
fill(cx,cx+maxn,-1);
fill(cy,cy+maxn,-1);
fill(first,first+maxn,-1);
edge_num=0;
ans=0;
}
inline void AddEdge(int a, int b)
{
edge[edge_num].b=b;
edge[edge_num].next=first[a],first[a]=edge_num++;
}
inline bool BFS()
{
int i,j,k;
bool flag(0);
int h,t;
memset(distx,0,sizeof(distx));
memset(disty,0,sizeof(disty));
h=t=0;
for(i=1;i<=nx;++i)
if(cx[i]==-1)que[t++]=i;
for(;h!=t;++h)
{
i=que[h];
for(k=first[i];k!=-1;k=edge[k].next)
{
j=edge[k].b;
if(!disty[j])
{
disty[j]=distx[i]+1;
if(cy[j]==-1)flag=1;
else distx[cy[j]]=disty[j]+1,que[t++]=cy[j];
}
}
}
return flag;
}
bool DFS(int i)
{
int j,k;
for (k=first[i];k!=-1;k=edge[k].next)
{
j=edge[k].b;
if(disty[j]==distx[i]+1)
{ // j i .
disty[j]=0; // j , .
if(cy[j]==-1||DFS(cy[j]))
{
cx[i]=j,cy[j]=i;
return 1;
}
}
}
return 0;
}
inline void Hopcroft_Karp()
{
int i,j;
while(BFS())
for(i=1;i<=nx;++i)
if(cx[i]==-1 && DFS(i))++ans;
}
int main(void)
{
// freopen("Input.txt", "r", stdin);
int i, j;
int a, b,p;
while (scanf("%d%d",&nx,&ny)!=EOF)
{
Init();
scanf("%d",&p);
for(i=1;i<=p;++i)
{
scanf("%d%d",&a,&b);
AddEdge(a, b);
}
Hopcroft_Karp();
printf("%d
", ans);
}
return 0;
}