【题解】 bzoj1191: [HNOI2006]超级英雄Hero （二分图）

Solution:

二分图最大匹配板子题

Attention:

注意题干中的一句话

只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰。

Code:

//It is coded by Ning_Mew on 5.12

#include<bits/stdc++.h>

using namespace std;

const int maxn=1007;

int n,m,ans=0;

int be[maxn];

bool vis[maxn];

int head[maxn],cnt=0;

struct Edge{

  int nxt,to;

}edge[maxn*2];

void add(int from,int to){

  edge[++cnt].nxt=head[from];edge[cnt].to=to;head[from]=cnt;

}

bool find(int u){

  for(int i=head[u];i!=0;i=edge[i].nxt){

    int v=edge[i].to;

    if(!vis[v]){

      vis[v]=true;

      if(be[v]==-1||find(be[v])){

	be[v]=u;return true;

      }

    }

  }return false;

}

int main(){

  scanf("%d%d",&n,&m);

  for(int i=1;i<=m;i++){

    int x,y;scanf("%d%d",&x,&y);

    add(i,x);add(i,y);

  }

  memset(be,-1,sizeof(be));

  for(int i=1;i<=m;i++){

    memset(vis,false,sizeof(vis));

    if(find(i))ans++;

    else break;

  }

  printf("%d\n",ans);

  return 0;

}

巴特西

【题解】 bzoj1191: [HNOI2006]超级英雄Hero （二分图）

Solution:

Attention:

Code:

最新文章

热门文章