首页 > 代码库 > 【匈牙利算法】 二分图模板 poj 1274
【匈牙利算法】 二分图模板 poj 1274
#include <iostream>#include <cstdio>#include <memory.h>using namespace std;int n,m,num,temp,sum;int re[201][201],link[201];//牛与牛栏的对应关系bool tag[201];//增益路径bool DFS(int a){ for(int i=1;i<=m;i++) { if(re[a][i]!=0 && !tag[i])//如果节点i与a相邻并且未被查找过 { tag[i]=true;//标记i为已查找过 if(link[i]==-1||DFS(link[i]))//i在匹配M中,但是从与i相邻的节点出发可以有增广路 { link[i]=a;//记录查找成功记录// cout << "sucess i=" << i << " link[i]= "<<link[i] <<endl; return true;//返回查找成功 } } } return false;}int main(){ //freopen("in.txt","r",stdin); while(cin>>n>>m) // cow stall { int i,j,sum=0; memset(re,0,sizeof(re)); memset(link,-1,sizeof(link)); for(i=1;i<=n;i++) { cin>>num; for(j=1;j<=num;j++) { cin>>temp; re[i][temp]=1; } }//初始化 for(i=1;i<=n;i++) //cow { for(j=1;j<=m;j++) //stall { tag[j]=false; } if(DFS(i))//从节点i尝试扩展 sum++; } cout << sum << endl; } return 0;}
【匈牙利算法】 二分图模板 poj 1274
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。