| Time Limit: 2000MS | Memory Limit: 30000K | |
| Total Submissions: 12810 | Accepted: 4632 | |
| Case Time Limit: 1000MS | ||
Description
Input
Output
Sample Input
2 3 2 0 3 2 1 1 3 0 3 2 0 2 3 0 1 0 1 2 1 0 2 1 0 0 2 0
Sample Output
2
题意：有k台挤奶器，c头 奶牛，每台挤奶每天能挤m头奶牛。接下来k+c行，每行有k+c个数(例如题中，标号1-2为挤奶器，标号3-5为奶牛)，所以第一行代表1号距离1号挤奶器距离为0，距离二号挤奶器的距离为3，距离3号奶牛的距离为2，距离4号奶牛的距离为1，距离5号奶牛的距离为1.(PS：英语渣看了好久才明白题意)。要求所有奶牛到达挤奶器所经过的最大路程中最小的距离。
思路：要说网络流最重要是要建图，先对输入的图用floyd求最小路径，然后找出奶牛和挤奶器之间的最大边maxx，从【0，maxx】中用二分查找最大边，根据最大边重新建图，然后用最大流判断这条边是否满足不超过挤奶器容量的条件。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
using namespace std;
const int inf=0x3f3f3f3f;
int head[310],num[310],d[310],pre[310],q[310],cur[310];
int dp[310][310];
int n,m,cnt,s,t,nv,c;
int maxint=inf;
struct node {
int u, v, cap;
int next;
} edge[1000000];
void add(int u, int v, int cap)
{
edge[cnt].v=v;
edge[cnt].cap=cap;
edge[cnt].next=head[u];
head[u]=cnt++;
edge[cnt].v=u;
edge[cnt].cap=0;
edge[cnt].next=head[v];
head[v]=cnt++;
}
void floyd()
{
int i, j, k;
for(k=1; k<=n; k++)
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
void bfs()
{
memset(num,0,sizeof(num));
memset(d,-1,sizeof(d));
int f1=0, f2=0, i;
d[t]=0;
num[0]=1;
q[f1++]=t;
while(f1>=f2) {
int u=q[f2++];
for(i=head[u]; i!=-1; i=edge[i].next) {
int v=edge[i].v;
if(d[v]==-1) {
d[v]=d[u]+1;
num[d[v]]++;
q[f1++]=v;
}
}
}
}
int isap()
{
memcpy(cur,head,sizeof(cur));
bfs();
int flow=0, u=pre[s]=s, i;
while(d[s]<nv) {
if(u==t) {
int f=maxint, pos;
for(i=s; i!=t; i=edge[cur[i]].v) {
if(f>edge[cur[i]].cap) {
f=edge[cur[i]].cap;
pos=i;
}
}
for(i=s; i!=t; i=edge[cur[i]].v) {
edge[cur[i]].cap-=f;
edge[cur[i]^1].cap+=f;
}
flow+=f;
u=pos;
}
for(i=cur[u]; i!=-1; i=edge[i].next) {
if(d[edge[i].v]+1==d[u]&&edge[i].cap) {
break;
}
}
if(i!=-1) {
cur[u]=i;
pre[edge[i].v]=u;
u=edge[i].v;
} else {
if(--num[d[u]]==0) break;
int mind=nv;
for(i=head[u]; i!=-1; i=edge[i].next) {
if(mind>d[edge[i].v]&&edge[i].cap) {
mind=d[edge[i].v];
cur[u]=i;
}
}
d[u]=mind+1;
num[d[u]]++;
u=pre[u];
}
}
return flow;
}
int main()
{
int k, m, i, j, x, ans;
while(~scanf("%d %d %d",&k,&c,&m)) {
n=k+c;
for(i=1; i<=n; i++) {
for(j=1; j<=n; j++) {
scanf("%d",&dp[i][j]);
if(dp[i][j]==0)
dp[i][j]=maxint;
}
}
floyd();
int low=1,high=40000, mid;
while(low<=high) {
mid=(high+low)/2;
s=0;
t=n+1;
nv=t+1;
memset(head,-1,sizeof(head));
cnt=0;
for(i=1; i<=k; i++)
add(s,i,m);
for(i=1; i<=c; i++)
add(k+i,t,1);
for(i=1; i<=k; i++)
for(j=1; j<=c; j++) {
if(dp[i][k+j]<=mid)
add(i,k+j,1);
}
x=isap();
if(x>=c) {
ans=mid;
high=mid-1;
} else if(x<c) {
low=mid+1;
}
}
printf("%d\n",ans);
}
return 0;
}
POJ 2112-Optimal Milking(网络流_最大流+floyd+二分查找)
原文：http://blog.csdn.net/u013486414/article/details/42875069