HDU 1068 Girls and Boys
问题分析
给与 多组 可能存在关系 要求找出 最少没有配对的人
利用二分图法 匈牙利算法 编号指向另一个编号看做一条边
求出最大可以匹配 的 对数
详解看代码
AC代码如下
#include<iostream>
#include<cstring>
#include<cstdio>//scanf printf 所在 必须加....深受其害
//或者直接万能头 #include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int nn=1005;
int n,m;
int path[nn][nn]; //可能关系 标记数组
bool flag[nn]; // 访问 数组（具体看后面code）
int match[nn]; //恋爱关系 指向数组
int dfs(int i)
{
for(int j=0;j<n;j++)
{
if(!flag[j]&&path[i][j]){
//这个男的没有被搜索过 并且 存在 可能的恋爱关系
flag[j]=1;//标记
if(match[j]==-1||dfs(match[j])){
// 可能 会出现2种情况
/*1. 这个男的在之前没有和任何女的建立关系
2. 已经 有关系了 但是 他通过 dfs能找到一个 没有和任何人
建立关系的女的
3. 都没有 j++ 下一个男士.....
*/
match[j]=i;
return 1;//建立了 关系
}
}
}
return 0;
}
int main()
{
while(~scanf("%d",&n)){
memset(path,0,sizeof(path));//每组重置 可能关系
memset(match,-1,sizeof(match));//重置 配对
for(int i=0;i<n;i++){
int x,y;
scanf("%d: (%d)",&x,&m);
while(m--){
scanf("%d",&y);
path[x][y]=1; //建立男女关系
}
}
int sum=0; //统计数组
for(int i=0;i<n;i++){
memset(flag,0,sizeof(flag));
//重置 男的 被选了
//为啥要重置？--> 因为 核心思想就是 替换
//如果不重置在 dfs时 第一道门槛给卡注了..
if(dfs(i))
sum++;
cout<<n-sum/2<<endl;
// 总数 减去最大匹配/2 即使 答案
//我们统计的 是 男女 和 女男
//因为 没有 明确的 界限 并且 在 dfs过程中 男女 都是交叉循环出现的（如果存在 dfs( match() )）
}
}
return 0;
}
