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


原题链接
一眼二分图匹配.一直加点,加到答不下去了就输出答案.

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

发表评论

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