很标准的二分匹配,用的是匈牙利算法。
#include<iostream>
#include<string>
using namespace std;
int key[1000][1000],total,count; //count是所有点能找到增广路径的 total是总人数
int ok[1000]; //记录右边所有的已经匹配的点,ok[i]=j右边第i个与左边第j个匹配
int rightt[1000]; //记录在一次递归中,右边各点是否已经匹配
int route(int );
int main()
{
int a,b,c;
string no;
char m;
while(cin>>total)
{
count=0;
memset(key,0,sizeof(key));
for(int i=0;i<total;i++)
{
cin>>a>>m>>m>>b>>m;
for(int j=0;j<b;j++)
{
scanf("%d",&c);
key[a][c]=1;
}
}
memset(ok,-1,sizeof(ok));
for(i=0;i<total;i++) //每个点为起点,都找一次增广路径
{
memset(rightt,0,sizeof(rightt));
if(route(i))
count++;
}
cout<<total-count/2<<endl;
}
return 0;
}
int route(int i)
{
for(int j=0;j<total;j++)
{
if(key[i][j]&&!rightt[j]) //j点在这次递归中,没有被访问过
{
rightt[j]=1;
if(ok[j]==-1||route(ok[j]))
{
ok[j]=i;
return 1;
}
}
}
return 0;
}
分享到:
相关推荐
HDUACM2010版13二分匹配及其应用.ppt
HDU二分匹配及其应用,此PPT是刘春英老师版权所有, 特此贡献给广大编程爱好者,特别是对于ACMer
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
hdu acm 教案 二分匹配及其应用 hdu acm 教案 二分匹配及其应用
HDU图论题目分类
hdu题目分类
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法
你活的不容易,我活的不容易,他活的也不容易。不过,如果你看了下面的故事,就会知道,有位老汉比你还不容易。
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划...(lecture_12)二分匹配及其应用 (lecture_13)动态规划(2) 并查集
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
其中有pku、hdu、zoj等各大oj的题目分类,pku的oj比较详细一点,按不同算法进行分类,均系从网上自行搜集的。
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门