网络流经典模型之——牛与牛棚

    模型：

    有n个牛棚和连接n个牛棚的m条路径，n<=200,m<=1500。每到下雨天，牛都很讨厌自己的蹄子被打湿，所以在下雨前都要躲进牛棚里。当然，每个牛棚能容纳的牛的数量有限。现在每个棚内有若干只牛，问最短需要多少时间，使得所有牛都能躲到牛棚里去。

    解：求最短时间，可以想到二分，然后判断可行性。

首先在原图上求floyd，得到每两个棚之间的最短距离。拆点：将每个棚拆为i和i'(流进的点和流出的点)，添边(i,i',INF)。增加源点s和汇点t，从s连边到i，容量为该棚现在的牛的数量，i'连边到t，容量为该棚的容量。接下来最关键的地方：若棚i和棚j之间的距离不大于t，则连边(i,j',INF),(j,i',INF)。仔细想想为什么不是(i',j,INF)和(j',i,INF)。因为棚i的牛要跑到棚j去避雨，显然是从i棚的入点到j棚的出点。

    求最大流，若从s发出的边均满流，则在low和mid中搜索；否则在mid和high中搜索。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxv = 205*2;
const int maxe = maxv*maxv*2;
int f,p;
int num[maxv],c[maxv];
long long g[maxv][maxv];
int sum;

struct Edge
{
    int v;
    int next;
    int flow;
};
Edge e[maxe];
int head[maxv],edgeNum;
int now[maxv],d[maxv],vh[maxv],pre[maxv],preh[maxv];

void addEdge(int a,int b,int c)
{
    e[edgeNum].v = b;
    e[edgeNum].flow = c;
    e[edgeNum].next = head[a];
    head[a] = edgeNum++;
    e[edgeNum].v = a;
    e[edgeNum].flow = 0;
    e[edgeNum].next = head[b];
    head[b] = edgeNum++;
}

void Init()
{
    edgeNum = 0;
    memset(head,-1,sizeof(head));
    memset(d,0,sizeof(d));
}

int sap(int s,int t,int n)       //源点，汇点，结点总数
{
    int i,x,y;
    int f,ans = 0;
    for(i = 0; i < n; i++)
        now[i] = head[i];
    vh[0] = n;
    x = s;
    while(d[s] < n)
    {
        for(i = now[x]; i != -1; i = e[i].next)
            if(e[i].flow > 0 && d[y=e[i].v] + 1 == d[x])
                break;
            if(i != -1)
            {
                now[x] = preh[y] = i;
                pre[y] = x;
                if((x=y) == t)
                {
                    for(f = INF,i=t; i != s; i = pre[i])
                        if(e[preh[i]].flow < f)
                            f = e[preh[i]].flow;
                    ans += f;
                    do
                    {
                        e[preh[x]].flow -= f;
                        e[preh[x]^1].flow += f;
                        x = pre[x];
                    }while(x!=s);
                }
            }
            else
            {
                if(!--vh[d[x]])
                    break;
                d[x] = n;
                for(i=now[x]=head[x]; i != -1; i = e[i].next)
                {
                    if(e[i].flow > 0 && d[x] > d[e[i].v] + 1)
                    {
                        now[x] = i;
                        d[x] = d[e[i].v] + 1;
                    }
                }
                ++vh[d[x]];
                if(x != s)
                    x = pre[x];
            }
    }
    return ans;
}

void floyd()
{
    int i,j,k;
    for(k = 1; k <= f; k++)
    {
        for(i = 1; i <= f; i++)
        {
            for(j = 1; j <= f; j++)
            {
                if(k!=i&&k!=j&&i!=j&&g[i][k]+g[k][j]<g[i][j])
                    g[i][j] = g[i][k] + g[k][j];
            }
        }
    }
}

int build(long long mid)
{
    int i,j;
    Init();
    int source = 0;
    int sink = 2*f+1;
    for(i = 1; i <= f; i++)
    {
        addEdge(source,i,num[i]);
        addEdge(i+f,sink,c[i]);
        addEdge(i,i+f,INF);
        for(j = 1; j <= f; j++)
            if(i!=j&&g[i][j]!=1000000000000&&g[i][j]<=mid)
                addEdge(i,j+f,INF);     //*********
    }
    return sap(source,sink,sink+1);
}

long long solve()
{
    long long low = 0;
    long long high = 1000000000000;
    long long mid;
    long long ans=-1;
    while(low<=high)
    {
        mid = (low+high)>>1LL;
        if(build(mid)==sum)
        {
            ans = mid;
            high = mid - 1;
        }
        else
            low = mid + 1;
    }
    return ans;
}

int main()
{
    int i,j;
    int a,b,w;
    scanf("%d %d",&f,&p);
    for(i = 1; i <= f; i++)
        for(j = 1; j <= f; j++)
            g[i][j] = 1000000000000;
    sum = 0;
    for(i = 1; i <= f; i++)
    {
        scanf("%d %d",&num[i],&c[i]);
        sum += num[i];
    }
    for(i = 0; i < p; i++)
    {
        scanf("%d %d %d",&a,&b,&w);
        if(g[a][b] > w)
            g[a][b] = g[b][a] = w;
    }
    floyd();
    printf("%lld\n",solve());
    return 0;
}