学步园

一开始题目意思理解错了，其实是要求每个group最多能有几个人，我去找最大group的编号了。。。囧,size居然被我理解成那个意思。。。

正确理解题目意思后，二分答案，枚举最大值，源点与每个人连容量为1的边，每个人与他可以呆的组连一条边，然后将每个组与汇点连线，容量为枚举的最大值，如果满流就减小最大值，否则扩大最大值

代码：

#include<iostream><br /> using namespace std;<br /> #define min(x,y) (x)<(y)?(x):(y)<br /> #define inf 99999999<br /> #define MAX 1600<br /> struct node<br /> {<br /> int x,y,c,op,next;<br /> }g[1000000];<br /> int map[MAX][605],dis[MAX],pre[MAX];<br /> int num[MAX],cur[MAX],adj[MAX],in[MAX];<br /> int m,n,S,T,vn,max_flow,e,l,r;<br /> void add(int x,int y,int c)<br /> {<br /> e++;<br /> g[e].x=x; g[e].y=y; g[e].c=c; g[e].op=e+1; g[e].next=adj[x]; adj[x]=e;<br /> e++;<br /> g[e].x=y; g[e].y=x; g[e].c=0; g[e].op=e-1; g[e].next=adj[y]; adj[y]=e;<br /> }<br /> void relabel(int k)<br /> {<br /> int i,mm=vn;<br /> cur[k]=adj[k];<br /> for(i=adj[k];i;i=g[i].next)<br /> {<br /> if(g[i].c>0)<br /> mm=min(mm,dis[g[i].y]);<br /> }<br /> dis[k]=mm+1;<br /> }<br /> void change()<br /> {<br /> int nf=inf,i;<br /> for(i=T;i!=S;i=g[pre[i]].x)<br /> {<br /> nf=min(nf,g[pre[i]].c);<br /> }<br /> for(i=T;i!=S;i=g[pre[i]].x)<br /> {<br /> g[pre[i]].c-=nf;<br /> g[g[pre[i]].op].c+=nf;<br /> }<br /> max_flow+=nf;<br /> }<br /> void sap()<br /> {<br /> int i;<br /> for(i=1;i<=vn;i++)<br /> {<br /> dis[i]=0;<br /> num[i]=0;<br /> cur[i]=adj[i];<br /> }<br /> num[0]=vn;<br /> i=S;<br /> while(dis[S]<vn)<br /> {<br /> for(;cur[i];cur[i]=g[cur[i]].next)<br /> {<br /> if(g[cur[i]].c>0&&dis[i]==dis[g[cur[i]].y]+1)<br /> break;<br /> }<br /> if(!cur[i])<br /> {<br /> num[dis[i]]--;<br /> if(num[dis[i]]==0)<br /> break;<br /> relabel(i);<br /> num[dis[i]]++;<br /> if(i!=S)<br /> i=g[pre[i]].x;<br /> }<br /> else<br /> {<br /> pre[g[cur[i]].y]=cur[i];<br /> i=g[cur[i]].y;<br /> if(i==T)<br /> {<br /> change();<br /> i=S;<br /> }<br /> }<br /> }<br /> }<br /> bool check(int limit)<br /> {<br /> int i,j;<br /> e=0;<br /> memset(adj,0,sizeof(adj));<br /> S=n+m+1;<br /> T=n+m+2;<br /> vn=T;<br /> for(i=1;i<=n;i++)<br /> for(j=1;j<=m;j++)<br /> {<br /> if(map[i][j])<br /> {<br /> add(i,n+j,1);<br /> }<br /> }<br /> for(i=1;i<=n;i++)<br /> add(S,i,1);<br /> for(i=1;i<=m;i++)<br /> {<br /> add(i+n,T,limit);<br /> }<br /> max_flow=0;<br /> sap();<br /> if(max_flow==n)<br /> return true;<br /> else<br /> return false;<br /> }<br /> void partition()<br /> {<br /> int i,mid,ans;<br /> l=0;<br /> r=-1;<br /> for(i=1;i<=m;i++)<br /> if(in[i]>r)<br /> r=in[i];<br /> while(l<=r)<br /> {<br /> mid=(l+r)/2;<br /> if(check(mid))<br /> {<br /> ans=mid;<br /> r=mid-1;<br /> }<br /> else<br /> l=mid+1;<br /> }<br /> printf("%d/n",ans);<br /> }<br /> int main()<br /> {<br /> int i,t;<br /> char name[20],c;<br /> while(scanf("%d%d",&n,&m)&&m&&n)<br /> {<br /> memset(map,0,sizeof(map));<br /> memset(in,0,sizeof(in));<br /> for(i=1;i<=n;i++)<br /> {<br /> scanf("%s",&name);<br /> t=0;<br /> getchar();<br /> while(scanf("%c",&c))<br /> {<br /> if(c==10)<br /> {<br /> map[i][++t]=1;<br /> in[t]++;<br /> t=0;<br /> break;<br /> }<br /> if(c==' ')<br /> {<br /> map[i][++t]=1;<br /> in[t]++;<br /> t=0;<br /> }<br /> else<br /> t=t*10+c-'0';<br /> }<br /> }<br /> partition();<br /> }<br /> return 0;<br /> }