BZOJ1191: [HNOI2006]超级英雄Hero

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1191

Solution

二分图模板。
把“锦囊妙计”和相应的问题连边，做一遍最大匹配就行了。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll int
#define N 1005
using namespace std;
struct edge{
    ll to,next;
}e[N*2];
ll head[N],flag[N],link[N],n,m,ans,tot;
void add(ll u,ll v){
    e[++tot]=(edge){v,head[u]}; head[u]=tot;
}
bool find(ll u){
    for (ll i=head[u],v=e[i].to;i;i=e[i].next,v=e[i].to)
        if (!flag[v]){
            flag[v]=1;
            if (!link[v]||find(link[v])){
                link[v]=u; return 1;
            }
        }
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    for (ll i=1;i<=m;i++){
        ll u,v;
        scanf("%d%d",&u,&v);
        add(i,u); add(i,v);
    }
    for (ll i=1;i<=n;i++){
        memset(flag,0,sizeof flag);
        if (find(i)) ans++; else break;
    }
    printf("%d",ans);
}