poj 2289(二分多重匹配+二分)

  1 /**************************************************
  2  * Author     : xiaohao Z
  3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
  4  * Last modified : 2014-02-23 15:21
  5  * Filename     : t2.cpp
  6  * Description     : 
  7  * ************************************************/
  8 
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <cstdlib>
 13 #include <cmath>
 14 #include <algorithm>
 15 #include <queue>
 16 #include <stack>
 17 #include <vector>
 18 #include <set>
 19 #include <map>
 20 #define MP(a, b) make_pair(a, b)
 21 #define PB(a) push_back(a)
 22     
 23 using namespace std;
 24 typedef long long ll;
 25 typedef pair<int, int> pii;
 26 typedef pair<unsigned int,unsigned int> puu;
 27 typedef pair<int, double> pid;
 28 typedef pair<ll, int> pli;
 29 typedef pair<int, ll> pil;
 30 
 31 const int INF = 0x3f3f3f3f;
 32 const double eps = 1E-6;
 33 const int MAXN = 1010;
 34 const int MAXM = 510;
 35 int uN,vN;
 36 int g[MAXN][MAXM];
 37 int linker[MAXM][MAXN];
 38 bool used[MAXM];
 39 char name[1010][101];
 40 int num[MAXM];//右边最大的匹配数
 41 
 42 bool dfs(int u)
 43 {
 44     for(int v = 0; v < vN; v++)
 45         if(g[u][v] && !used[v])
 46         {
 47             used[v] = true;
 48             if(linker[v][0] < num[v])
 49             {
 50                 linker[v][++linker[v][0]] = u;
 51                 return true;
 52             }
 53             for(int i = 1; i <= num[0]; i++)
 54                 if(dfs(linker[v][i]))
 55                 {
 56                     linker[v][i] = u;
 57                     return true;
 58                 }
 59         }
 60     return false;
 61 }
 62 
 63 int hungary()
 64 {
 65     int res = 0;
 66     for(int i = 0; i < vN; i++)
 67         linker[i][0] = 0;
 68     for(int u = 0; u < uN; u++)
 69     {
 70         memset(used,false,sizeof(used));
 71         if(dfs(u))res++;
 72     }
 73     return res;
 74 }
 75 
 76 bool J(int m){
 77     for(int i=0; i<vN; i++) num[i] = m;
 78     int ret = hungary();
 79     if(ret == uN) return true;
 80     else return false;
 81 }
 82 
 83 int main()
 84 {
 85 //    freopen("in.txt", "r", stdin);
 86 
 87     int vex;
 88     while(scanf("%d%d", &uN, &vN)!=EOF){
 89         if(!uN && !vN) break;
 90         memset(g, 0, sizeof g);
 91         for(int i=0; i<uN; i++){
 92             scanf("%s", name[i]);
 93             while(getchar()!=‘\n‘){
 94                 scanf("%d", &vex);     
 95                 g[i][vex] = 1;
 96             }
 97         }
 98         int l = 0, r = uN;
 99         while(l < r){
100             int m = (l+r)/2;
101             if(J(m)) r = m;     
102             else l = m+1; 
103         }
104         printf("%d\n", l);
105     }
106     return 0;
107 }