SPOJ4206Fast Maximum Matching(hopcroft-karp)

タイトルはこちらを押してください
裸の二分マッチ.
テーマ分析:データが比較的に強く、テンプレートを測定するために使用されます.この問題はhungryで走るのは骨が折れるのでhopcroft-karpアルゴリズムを使います.このアルゴリズムがhungryより効率的であるのは,bfsのたびに1つの拡張路セットを見つけ,その後dfsを用いて多重拡張を行い,同時に複数の拡張路を探し,効率が大幅に増加するためである.実はどのようにhkアルゴリズムを見ても辺権のないdinicですね.
wikipediaを参照してhkを1つ叩いて、効率は高くないようですね...
詳細はコードを参照してください.
 

#include <iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N = 50001;

const int M = 150001;

const int inf = 0x3f3f3f3f;



int head[N];

struct node

{

    int to,next;

}g[M];

int m,n,p,num;

int matchx[N],matchy[N],que[N],dis[N];

void build(int s,int e)

{

    g[num].to = e;

    g[num].next = head[s];

    head[s] = num ++;

}

bool bfs()

{

    int i,j;

    int front,rear;

    front = rear = 0;

    for(i = 1;i <= n;i ++)

    {

        if(!matchx[i])

        {

            dis[i] = 0;

            que[rear ++] = i;

        }

        else

            dis[i] = inf;

    }

    dis[0] = inf;

    while(front != rear)

    {

        int u = que[front ++];

        if(front == N)

            front = 0;

        for(i = head[u];~i;i = g[i].next)

        {

            int v = g[i].to;

            if(dis[matchy[v]] == inf)

            {

                dis[matchy[v]] = dis[u] + 1;

                que[rear ++] = matchy[v];

                if(rear == N)

                    rear = 0;

            }

        }

    }

    return dis[0] != inf;

}

bool dfs(int u)

{

    int i,v;

    for(i = head[u];~i;i = g[i].next)

    {

        v = g[i].to;

        if(dis[matchy[v]] == dis[u] + 1)

            if(matchy[v] == 0 || dfs(matchy[v]))

            {

                matchx[u] = v;

                matchy[v] = u;

                return true;

            }

    }

    dis[u] = inf;

    return false;

}



void Hopcroft_Karp()

{

    memset(matchx,0,sizeof(matchx));

    memset(matchy,0,sizeof(matchy));

    int ans = 0;

    while(bfs())

    {

        for(int i = 1;i <= n;i ++)

            if(!matchx[i])

                if(dfs(i))

                    ans ++;

    }

    printf("%d
",ans);

}

int main()

{

    int a,b;

    while(scanf("%d",&n) != EOF)

    {

        memset(head,-1,sizeof(head));

        num = 1;

        scanf("%d%d",&m,&p);

        while(p --)

        {

            scanf("%d%d",&a,&b);

            build(a,b);

        }

        Hopcroft_Karp();

    }

    return 0;

}