[BZOJ1191][HNOI2006]超级英雄Hero 二分图匹配



一眼二分图.注意要找的是第一个匹配不上的点,而不是最大匹配.
今天终于写了一次匈牙利,在本题中可以免掉Dinic需要的二分步骤.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 10233
#define M 10233
using namespace std;
int n,m,head[N],to[M],nxt[M],tot,ans;
inline void add(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
int vis[N],flag[N];
int find(int x)
{
    for(int i=head[x];i;i=nxt[i])if(!vis[to[i]])
    {
        vis[to[i]]=1;
        if(flag[to[i]]==0||find(flag[to[i]]))
        {
            flag[to[i]]=x;
            return 1;
        }
    }
    return false;
}
int main()
{
    cin>>n>>m;
    for(int x,y,i=1;i<=m;++i)
    {
        memset(vis,0,sizeof vis);
        scanf("%d%d",&x,&y);
        x++,y++;
        add(i,x+m);
        if(y!=x)add(i,y+m);
        if(!find(i))
        {
            printf("%d\n",i-1);
            return 0;
        }
    }
    printf("%d\n",m);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注