#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define N 2000 #define M 1000010 #define inf 1<<30 using namespace std; struct Edge{ int to,val,next; }edge[M]; int index[N],d[N],gap[N],e,list[N][510]; void addedge(int from,int to,int val) { edge[e].to=to; edge[e].val=val; edge[e].next=index[from]; index[from]=e++; edge[e].to=from; edge[e].val=0; edge[e].next=index[to]; index[to]=e++; } int source,des,n,m; int dfs(int pos,int flow) { if(pos==des) return flow; int i,j,v,val,lv,mind,c; mind=n-1;//初始最小标号为n-1 lv=flow; for(i=index[pos];i!=-1;i=edge[i].next) { v=edge[i].to; val=edge[i].val; if(val) { if(d[v]+1==d[pos]) { c=min(lv,val);//对于该点的最小可行流 c=dfs(v,c); edge[i].val-=c;//更新剩余图 edge[i^1].val+=c; lv-=c; if(d[source]>=n)return flow-lv; if(lv==0) break; } if(d[v]<mind)mind=d[v];//找出与pos相连的点的最小标号 } } if(lv==flow)//没有找到增广路劲，进行标号更新 { --gap[d[pos]]; if(!gap[d[pos]]) d[source]=n; d[pos]=mind+1; ++gap[d[pos]]; } return flow-lv; } int sap(int st,int de) { source=st; des=de; memset(d,0,sizeof(d)); memset(gap,0,sizeof(gap)); gap[0]=n;//初始标号为0的有n个. int ans=0; while(d[st]<n) { ans+=dfs(st,inf); //cout<<d[st]<<endl; } return ans; } void init() { e=0; memset(index,-1,sizeof(index)); memset(list,0,sizeof(list)); } // n is the number of point int main() { int i,j,k,num,pos; char str[20],c; while(scanf("%d%d",&n,&m)!=EOF,n||m) { init(); for(i=1;i<=n;i++) { pos=0; scanf("%s",&str); while(scanf("%c",&c),c!=' ') { scanf("%d",&k); list[i][pos++]=k; } list[i][pos]=-1; } num=n; n=n+m+2;//n是点的数目，一共n+m+2个点。包括源点和汇点 int l=1,r=1000,mid; while(l<r) { mid=(l+r)>>1; memset(index,-1,sizeof(index)); for(i=1;i<=num;i++) { addedge(0,i,1); pos=0; while(list[i][pos]!=-1) { addedge(i,num+list[i][pos++]+1,1); } } for(i=1;i<=m;i++) addedge(num+i,num+m+1,mid); int ans=sap(0,num+m+1); //cout<<ans<<endl; if(ans<num) l=mid+1,e=0; else r=mid,e=0; } printf("%d ",l); } return 0; }
建图方式：
建立一个超级源点和一个超级汇点，由源点向每个人(编号从1->n)建立一个流量为1的边，从每个人向每个他从属的组织建立一条流量为1的边，在由每个组织建立一条流向汇点的边，我们可以二分枚举组织向汇点边的流量。