网络流 POJ2112

题意：K个产奶机，C头奶牛，每个产奶机最多可供M头奶牛使用；并告诉了产奶机、奶牛之间的两两距离Dij(0<=i,j<K+C)。

问题：如何安排使得在任何一头奶牛都有自己产奶机的条件下，奶牛到产奶机的最远距离最短？最短是多少？

建图源点 -> 每头牛 -> 每个机器 -> 汇点

权 1 ? M

二分找最远距离里面最小的

二分距离 if dis[i][j]<dis 牛到机器的流量 1 也就是权

  1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<string.h>
  4 #include<queue>
  5 
  6 using namespace std;
  7 
  8 #define MAXN 300
  9 #define inf  100000000
 10 int k,c,m,n;
 11 int S,T;                  //我把源点和汇点 设成 0 n+1
 12 int dis[MAXN][MAXN];
 13 int z[MAXN][MAXN];
 14 int vis[MAXN];
 15 
 16 void floyed()
 17 {
 18     int i,j,k;
 19 
 20     for(k=1;k<=n;k++)
 21     {
 22         for(i=1;i<=n;i++)
 23         {
 24             for(j=1;j<=n;j++)
 25             {
 26                 if(dis[i][j]>dis[i][k]+dis[k][j])
 27                     dis[i][j]=dis[i][k]+dis[k][j];
 28             }
 29         }
 30     }
 31 }
 32 void makemap(int w)
 33 {
 34     int i,j;
 35     memset(z,0,sizeof(z));  //反向边这边已经有了
 36     for(i=k+1;i<=n;i++)
 37         z[0][i]=1;
 38     for(i=1;i<=k;i++)
 39         z[i][n+1]=m;
 40     for(i=k+1;i<=n;i++)
 41         for(j=1;j<=k;j++)
 42         {
 43             if(dis[i][j]<=w)
 44                 z[i][j]=1;
 45         }
 46 }
 47 int bfs()
 48 {
 49     memset(vis,-1,sizeof(vis));
 50     vis[S]=0;
 51     queue<int>q1;
 52     q1.push(S);
 53     int i;
 54     while(!q1.empty())
 55     {
 56         int now=q1.front();
 57         q1.pop();
 58         for(i=0;i<=n+1;i++)
 59         {
 60             if(vis[i]<0&&z[now][i])
 61             {
 62                 q1.push(i);
 63                 vis[i]=vis[now]+1;
 64             }
 65         }
 66     }
 67     return vis[T]!=-1;
 68 }
 69 int dfs(int u,int w)
 70 {
 71     int ans=0;
 72     if(u==T)
 73         return w;
 74     int i;
 75     for(i=0;i<=n+1;i++)
 76     {
 77         if(vis[i]==vis[u]+1&&z[u][i])
 78         {
 79             int b=dfs(i,min(z[u][i],w-ans));
 80             z[u][i]-=b;
 81             z[i][u]+=b;
 82             ans=ans+b;
 83         }
 84     }
 85     return ans;
 86 }
 87 
 88 int main()
 89 {
 90     while(scanf("%d%d%d",&k,&c,&m)!=EOF)
 91     {
 92         int i,j;
 93         n=k+c;
 94 
 95         for(i=1;i<=n;i++)
 96             for(j=1;j<=n;j++)
 97             {
 98                 scanf("%d",&dis[i][j]);
 99                 if(dis[i][j]==0)
100                     dis[i][j]=inf;
101             }
102         floyed();
103         int L,R;
104         L=0;
105         R=inf;
106         S=0;
107         T=n+1;
108         int ans=0;
109         while(L<=R)
110         {
111             int w=0,mid;
112             mid=(L+R)>>1;
113             makemap(mid);
114             while(bfs())
115                 w+=dfs(0,inf);
116             if(w>=c)
117             {
118                 ans=mid;
119                 R=mid-1;
120             }
121             else
122                 L=mid+1;
123         }
124 
125         printf("%d
",ans);
126     }
127 
128     return 0;
129 }