HDU1068匈牙利算法（最大独立集（最大匹配））

参考资料：
http://dsqiu.iteye.com/blog/1689505
https://www.byvoid.com/blog/hungary/


  1 /*HDU1068匈牙利算法
  2 思考过程：
  3 1、对没有好感的点之间连一条边。最后求最大团。
  4 2、对有好感度的点之间连一条无向边。最后求最大独立集。
  5 最大团是NP问题。
  6 这道题目因为特殊性：一条边连接的是一男一女，所以必然能用红蓝着色，分成两个集合，所以这也暗示了这个图是一个二分图
  7 这样我们用2中的思路来看，对于一条边连接的两个点，必然不能划分到一个集合中去。
  8 也就像在红蓝染色过程中，我们只能选择（尽可能）被染成同一种颜色的点。
  9 所以就是个求二分图最大独立点集（最大匹配）的问题.
 10 使用匈牙利算法，复杂度为O(MN)
 11 important：最大独立点集=最小覆盖路径= 顶点数 - 最大二分匹配/2
 12 匈牙利算法：
 13 伪代码：from byvoid
 14 bool 寻找从k出发的对应项出的可增广路
 15 {
 16     while (从邻接表中列举k能关联到顶点j)
 17     {
 18         if (j不在增广路上)
 19         {
 20             把j加入增广路;
 21             if (j是未盖点 或者 从j的对应项出发有可增广路)
 22             {
 23                 修改j的对应项为k;
 24                 则从k的对应项出有可增广路,返回true;
 25             }
 26         }
 27     }
 28     则从k的对应项出没有可增广路,返回false;
 29 }
 30 
 31 void 匈牙利hungary()
 32 {
 33     for i->1 to n
 34     {
 35         if (则从i的对应项出有可增广路)
 36             匹配数++;
 37     }
 38     输出 匹配数;
 39 }
 40 */
 41 #include <iostream>
 42 #include <cmath>
 43 #include <algorithm>
 44 #include <string.h>
 45 #include <stdio.h>
 46 #include <set>
 47 #include <stack>
 48 #include <vector>
 49 #define maxn 510
 50 using namespace std;
 51 
 52 vector<int> G[maxn];
 53 int match[maxn];//记录点的对应项
 54 bool visit[maxn];//记录点是否在增广路上
 55 
 56 int n;
 57 /* 7
 58 0: (3) 4 5 6*/
 59 void read(){
 60     for(int i=1;i<=n;i++) G[i].clear();
 61     for(int i=1;i<=n;i++){
 62         int a,k,b;
 63         scanf("%d:  (%d)",&a,&k);
 64         a++;
 65         for(int j=0;j<k;j++){
 66             scanf("%d",&b);
 67             b++;
 68             G[a].push_back(b);
 69         }
 70     }
 71     return ;
 72 }
 73 bool dfs(int s)//找到从s点出发的可增广路
 74 {
 75     for(int i=0;i<G[s].size();i++){
 76         int v=G[s][i];
 77         if (!visit[v]){
 78             visit[v]=true;
 79             if (match[v]==0 || dfs(match[v])){//说明v对应的项有增广路
 80                 match[v]=s;//修改v的对应项（即互斥点）是s
 81                 return true;
 82             }
 83         }
 84     }
 85     return false;
 86 }
 87 
 88 int hungary(){
 89     int ans=0;
 90     memset(match,0,sizeof(match));//清空匹配
 91     for(int i=1;i<=n;i++){
 92         memset(visit,0,sizeof(visit));//注意清空增广路
 93         if (dfs(i)) ans++;
 94     }
 95     return ans;
 96 }
 97 
 98 int main(){
 99     while(cin>>n){
100         read();
101         printf("%d
",n-hungary()/2);
102         //最大匹配
103     }
104     return 0;
105 }
重点：最大独立点集=最小覆盖路径= 顶点数 - 最大二分匹配/2