题目链接：

id=2391">poj2391

题意：

有n块草地,每块草地上有一定数量的奶牛和一个雨棚,并给出了每一个雨棚的容（牛）量.

有m条路径连接这些草地  ,这些路径是双向的，并且非常宽敞，能够容下无限条牛并排走, 给出经过每条路径所须要消耗的时间

问：全部牛都到达雨棚下的最小时间

解题思路：

类似    牛与挤奶器的问题

http://blog.csdn.net/axuan_k/article/details/45920969  已给出基本思路

与上题最大的差别是：

草地既连接源点，也连接汇点  并且草地与草地之间的路径是双向的.而网络流中的应该是单向的,

这就须要我们拆点了： 把每块草地拆成两个点 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;

}