HDU 1068 Girls and Boys

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;
}