题意：

　　一些人，和他们可能加入的组号。问每个组，最小的最大人数是多少

分析：

　　二分的是最大流的容量。设置一个超级源点，连向所有的人，容量为1。设置一个超级汇点，使所有的组连向超级汇点，二分的就是这里的容量（0～n）。然后根据题目给出的人和组的关系连接人和组，容量为1。二分时，若当前状态求出的最大流等于人数，则下界等于mid，若不等于，则上界等于mid。二分出的容量，就是组中的最小的最大人数。

输入：

3 2

John 0 1

Rose 1

Mary 1

5 4

ACM 1 2 3

ICPC 0 1

Asian 0 2 3

Regional 1 2

ShangHai 0 2

0 0 

输出：

2

2

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int maxn=3010;const int inf=1e9;int n,m;structEdge{ int u,v; int flow,cap; Edge(int uu,int cc,int fl,int ca):u(uu),v(cc),flow(fl),cap(ca) { }};vector
           
            edge;structISAP{ vector
            
             G[maxn]; vector
             
              edge; int s,t; int d[maxn]; int cur[maxn]; int p[maxn]; int num[maxn]; int flow; void init() { for(int i=0;i<=n+m+1;i++) G[i].clear(); s=0; t=n+m+1; } bool bfs() { memset(d,-1,sizeof(d)); queue
              
               q; q.push(t); d[t]=0; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0;i
               
                s=s; this->t=t; flow=0; bfs(); for(int i=0;i<=n+m+1;i++) num[d[i]]++; int x=s; memset(cur,0,sizeof(cur)); while(d[s]
                
                 e.flow&&d[x]==d[e.v]+1) { ok=true; p[e.v]=G[x][i]; cur[x]=i; x=e.v; break; } } if(!ok) { int k=n+m+1; for(int i=0;i
                 
                  e.flow) k=min(k,d[e.v]); } if(--num[d[x]]==0) break; num[d[x]=k+1]++; cur[x]=0; if(x!=s) x=edge[p[x]].u; } } return flow; }}solver;char buffer[11000];void add(int s,int t,int cap){ edge.push_back(Edge(s,t,0,cap)); edge.push_back(Edge(t,s,0,0)); int x=edge.size(); solver.G[s].push_back(x-2); solver.G[t].push_back(x-1);}void input(){ solver.init(); int x; edge.clear(); char ch[100]; for (int i = 1 ; i <= n ; ++i) { add(0,i,1); scanf("%*s"); gets(buffer); char * p = strtok(buffer, " "); while (p) { sscanf(p,"%d",&x); add(i,x+1+n,1); p = strtok(NULL," "); } } int sz=edge.size(); for(int i=n+1;i<=n+m;i++) { sz+=2; solver.G[i].push_back(sz-2); solver.G[n+m+1].push_back(sz-1); }}void build(int up){ solver.edge=edge; for(int i=n+1;i<=n+m;i++) { solver.edge.push_back(Edge(i,n+m+1,0,up)); solver.edge.push_back(Edge(n+m+1,i,0,0)); }}void solve(){ int left=1,right=n; int mid=(left+right)>>1; int ans=n; while(left<=right) { build(mid); if (solver.maxflow(0,n+m+1)==n) { right = mid-1; ans = min(ans,mid); } else { left = mid+1; } mid = (left+right)>>1; } printf("%d\n",ans);}int main(){ while(scanf("%d%d",&n,&m)==2,n+m) { input(); solve(); }}
                 
                
               
              
             
            
           
          
         
        
       
      
     
    

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int maxn=3010;const int inf=1e9;int n,m;structEdge{ int u,v; int flow,cap; Edge(int uu,int cc,int fl,int ca):u(uu),v(cc),flow(fl),cap(ca) { }};vector
           
            edge;structISAP{ vector
            
             G[maxn]; vector
             
              edge; int s,t; int d[maxn]; int cur[maxn]; int p[maxn]; int num[maxn]; int flow; void init() { for(int i=0;i<=n+m+1;i++) G[i].clear(); s=0; t=n+m+1; } bool bfs() { memset(d,-1,sizeof(d)); queue
              
               q; q.push(t); d[t]=0; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0;i
               
                s=s; this->t=t; flow=0; bfs(); for(int i=0;i<=n+m+1;i++) num[d[i]]++; int x=s; memset(cur,0,sizeof(cur)); while(d[s]
                
                 e.flow&&d[x]==d[e.v]+1) { ok=true; p[e.v]=G[x][i]; cur[x]=i; x=e.v; break; } } if(!ok) { int k=n+m+1; for(int i=0;i
                 
                  e.flow) k=min(k,d[e.v]); } if(--num[d[x]]==0) break; num[d[x]=k+1]++; cur[x]=0; if(x!=s) x=edge[p[x]].u; } } return flow; }}solver;char buffer[11000];void add(int s,int t,int cap){ edge.push_back(Edge(s,t,0,cap)); edge.push_back(Edge(t,s,0,0)); int x=edge.size(); solver.G[s].push_back(x-2); solver.G[t].push_back(x-1);}void input(){ solver.init(); int x; edge.clear(); char ch[100]; for (int i = 1 ; i <= n ; ++i) { add(0,i,1); scanf("%*s"); gets(buffer); char * p = strtok(buffer, " "); while (p) { sscanf(p,"%d",&x); add(i,x+1+n,1); p = strtok(NULL," "); } } int sz=edge.size(); for(int i=n+1;i<=n+m;i++) { sz+=2; solver.G[i].push_back(sz-2); solver.G[n+m+1].push_back(sz-1); }}void build(int up){ solver.edge=edge; for(int i=n+1;i<=n+m;i++) { solver.edge.push_back(Edge(i,n+m+1,0,up)); solver.edge.push_back(Edge(n+m+1,i,0,0)); }}void solve(){ int left=1,right=n; int mid=(left+right)>>1; int ans=n; while(left<=right) { build(mid); if (solver.maxflow(0,n+m+1)==n) { right = mid-1; ans = min(ans,mid); } else { left = mid+1; } mid = (left+right)>>1; } printf("%d\n",ans);}int main(){ while(scanf("%d%d",&n,&m)==2,n+m) { input(); solve(); }}