讨论 / 哪只牛能说说这题思路
tzh 2010-10-22 19:37:00
点我顶贴 收藏 删除
想了半天想出个越想越复杂的方法,所以干脆放弃,有会做的说说思路啊
#1 wanghao1996@2010-10-22 19:37:00
回复 删除
二分图的最大匹配

#2 REHYANG@2018-07-30 20:25:09
回复 删除
二分图的最大匹配

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

using namespace std;

#define N 100010

int n,m,p;

int vis[N],g[404][404],my[N];

void Read(){

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

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

while(1){

scanf("%d",&p);

if(!p) break;

g[i][p]=1;

}

}

}

bool dfs(int i){

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

if(g[i][j]==1&&vis[j]==0){

vis[j]=1;

if(my[j]==0 || dfs(my[j])){

my[j]=i;

return true;

}

}

}

return false;

}

void divide(){

int ans=0;

memset(my,0,sizeof(my));

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

memset(vis,0,sizeof(vis));

if(dfs(i))

ans++;

}

printf("%d",ans);

}

int main(){

Read();

divide();

return 0;

}

查看更多回复
提交回复