10
12
2015
0

[BZOJ1191] [HNOI2006] 超级英雄Hero

这一题是一个很裸的二分图。每次以当前的问题编号连接两个锦囊的编号,跑一遍二分图就可以了。

#include<cstdio>
#include<cstring>
  
int link[1005],n,m,h[1005],en,b[1005],ans;
  
struct Edge{
    int b,next; 
}e[1005];
  
void Add(int sa,int sb){
    e[++en].b=sb;
    e[en].next=h[sa];
    h[sa]=en;
}
  
int Find(int u){
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(b[v])continue;
    b[v]=1;
    if(!link[v] || Find(link[v])){
        link[v]=u;
        return 1;
    }
}
return 0;
}
  
int main(){
    freopen("1191.in","r",stdin);
    freopen("1191.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int sa,sb;
        scanf("%d %d",&sa,&sb);
        Add(i,sb+1);
        Add(i,sa+1);
    }
    for(int i=1;i<=m;i++){
        memset(b,0,sizeof(b));
        if(Find(i))ans++;
        else break;
    }
    printf("%d\n",ans);
    return 0;
}
Category: BZOJ | Tags: BZOJ | Read Count: 534

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com