hungary.cpp

匈牙利算法实现二分图最大匹配 文件输入输出.

#include <cstdio>
#include <cstring>

struct edge
{
        int id,v;
        edge *next;
        edge(int id,int v,edge *next):id(id),v(v),next(next) {}
} *e[201]={NULL};
bool used[201];
int match[201]={0},id[201]={0};

bool find(int v)
{
        for(edge *t=e[v];t;t=t->next)
                if(!used[t->v])
                {
                        used[t->v]=true;
                        if(!match[t->v]||find(match[t->v]))
                        {
                                match[t->v]=v;
                                id[t->v]=t->id;
                                return true;
                        }
                }
        return false;
}

int main()
{
    freopen("Hungary.in","r",stdin);
    freopen("Hungary.out","w",stdout);
    int n,m,k;
    scanf("%d %d %d",&n,&m,&k);
    int a,b,ans=0;
    for(int i=1;i<=k;++i)
    {
            scanf("%d %d",&a,&b);
            e[a]=new edge(i,b,e[a]);
    }
    for(int i=1;i<=n;++i)
    {
            memset(used,false,sizeof(used));
            if(find(i)) ++ans;
    }
    printf("%d\n",ans);
    for(int i=1;i<=m;i++)
            if(match)
                    printf("%d\n",id);
    return 0;
}