poj 2112 Optimal Milking 二分+最大流

<<训练指南>>P367页提到的公平分配问题。

二分答案ans

建模：

构造二分图，奶牛看成X集合，挤奶机看成Y集合。

1、X和源S连边，边容量为1.

2、满足dist(x,y)<=ans的 X和Y连边，边容量为1

3、Y和汇T连边，边容量为m.(不能超过挤奶机上限)

这样，网络中的流量都是由S――》X――》Y――》T点 ，只有当网络的总流量等于K时，才意味着每一个奶牛都选择了一个挤奶器，也就是一个可行解。

通过log（n）次的最大流既可以求出答案。

dinic实现。

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; #define MAXN 250 #define INF 0x3f3f3f3f struct edge { int to,c,next; }; edge e[999999]; int que[MAXN*100]; int dis[MAXN]; int pre[MAXN]; int head[MAXN],head2[MAXN]; int mp[MAXN][MAXN]; int st,ed; int maxflow; int en; int n,m,k,c; void add(int a,int b,int c) { e[en].to=b; e[en].c=c; e[en].next=head[a]; head[a]=en++; e[en].to=a; e[en].c=0; e[en].next=head[b]; head[b]=en++; } bool bfs() { memset(dis,-1,sizeof(dis)); que[0]=st,dis[st]=1; int t=1,f=0; while(f
      
       mp[i][k]+mp[k][j]) mp[i][j]=mp[i][k]+mp[k][j]; } } } } void build(int mid) { init(); for(int i=1;i<=k;i++) add(i,ed,m); for(int j=k+1;j<=k+c;j++) add(st,j,1); for(int i=k+1;i<=k+c;i++) { for(int j=1;j<=k;j++) { if(mp[i][j]<=mid) { add(i,j,1); } } } } int cal() { l=0;r=20000; int ans=0; while(l<=r) { mid=(l+r)>>1; build(mid); if(dinic()==c) {ans=mid;r=mid-1;} else l=mid+1; } return ans; } int main() { while(scanf("%d%d%d",&k,&c,&m)!=EOF) { input(); printf("%d\n",cal()); } }