题目链接：
poj2391
题意：
有n块草地,每块草地上有一定数量的奶牛和一个雨棚,并给出了每个雨棚的容（牛）量.
有m条路径连接这些草地 ,这些路径是双向的，而且很宽敞，可以容下无限条牛并排走, 给出经过每条路径所需要消耗的时间
问：所有牛都到达雨棚下的最小时间
解题思路：
类似 牛与挤奶器的问题
已给出基本思路
与上题最大的区别是：
草地既连接源点，也连接汇点 而且草地与草地之间的路径是双向的.而网络流中的应该是单向的,
这就需要我们拆点了： 把每块草地拆成两个点 i和n+i；且i到n+i的距离为0 ，只连接（1~n）->（n+1~2n）的边
这样,就和上题解法一样了
要注意的是: 时间可能大于 int；距离初值应赋为long long的无穷大
代码:
#include <iostream>#include <cstring>#include<cstdio>#define LL long long#include <queue>const int MAXN =1050;const int MAXM=440020;const int INF=0x3f3f3f3f;using namespace std;struct Edge{int to,cap,flow,next;} edge[MAXM];int head[MAXN],tot,gap[MAXN],d[MAXN],cur[MAXN],que[MAXN],p[MAXN];void init(){tot=0;memset(head,-1,sizeof(head));}void addedge(int u,int v,int c,int f){edge[tot]=(Edge){v,c,f,head[u]};head[u] = tot++;edge[tot]=(Edge){u,c,c,head[v]};head[v] = tot++;}int isap(int source,int sink,int N){memset(gap,0,sizeof(gap));memset(d,0,sizeof(d));memcpy(cur,head,sizeof(head));int top = 0,x = source,flow = 0;while(d[source] < N){if(x == sink){int Min = INF,inser=0;for(int i = 0; i < top; ++i){if(Min > edge[p[i]].cap – edge[p[i]].flow){Min = edge[p[i]].cap – edge[p[i]].flow;inser = i;}}for(int i = 0; i < top; ++i){edge[p[i]].flow += Min;edge[p[i]^1].flow -= Min;}if(Min!=INF) flow += Min;top = inser;x = edge[p[top]^1].to;continue;}int ok = 0;for(int i = cur[x]; i != -1; i = edge[i].next){int v = edge[i].to;if(edge[i].cap > edge[i].flow && d[v]+1 == d[x]){ok = 1;cur[x] = i;p[top++] = i;x = edge[i].to;break;}}if(!ok){int Min = N;for(int i = head[x]; i != -1; i = edge[i].next){if(edge[i].cap > edge[i].flow && d[edge[i].to] < Min){Min = d[edge[i].to];cur[x] = i;}}if(–gap[d[x]] == 0) break;gap[d[x] = Min+1]++;if(x != source) x = edge[p[–top]^1].to;}}return flow;}LL dis[MAXN][MAXN];int v[MAXN][2];void build(int n,LL value){init();for(int i=1; i<=n; i++){addedge(0,i,v[i][0],0);addedge(n+i,2*n+1,v[i][1],0);}for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)if(dis[i][j]<=value)addedge(i,n+j,INF,0);}int main(){// freopen("in.txt","r",stdin);int n,m,a,b;LL c;int sum=0,sum2=0;scanf("%d%d",&n,&m);for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(i != j) dis[i][j] = 2000000000000LL; //初始化long long的无穷大else dis[i][j] = 0;for(int i=1; i<=n; i++){scanf("%d%d",&v[i][0],&v[i][1]);sum+=v[i][0];sum2+=v[i][1];}for(int i=1; i<=m; i++){scanf("%d%d%lld",&a,&b,&c);if(dis[a][b]>c)//选最小的dis[a][b]=dis[b][a]=c;}if(sum>sum2){printf("-1\n");return 0;}for(int k=1; k<=n; k++)for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)if(dis[i][k]+dis[k][j]<dis[i][j])dis[i][j]=dis[k][j]+dis[i][k];LL ans=-1,l=0,r=1e12,mid;//注意这个r右边界 一定要比dis数组的初值小int d;while(l<=r){mid=(l+r)>>1;build(n,mid);d=isap(0,2*n+1,2*n+2);if(d==sum){ans=mid;r=mid-1;}else l=mid+1;}printf("%lld\n",ans);return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，心有多大，舞台就有多大
