学步园

题意： n块草地上有一定数量的牛，和一定数量牛棚，现在要让所有的牛进入牛棚，问牛的最长最短距离是多少。

解法： 将草地拆点，每块草地牛的数量与源点连边，牛棚数与汇点连边，拆开的两个点连一条无穷大的边。

用floyd跑一遍求出任意两点的最短距离，然后二分答案，每次重建图，将符合条件的边以容量INF加进容量网络里，跑一遍最大流，如果等于牛总数就更新答案，刷新上界，否则刷新下界。

数据比较变态，floyd要用__int64跑。

笔者卡这题两天，原因实在是SB啊：二分的上界开的Inf，当取到这个上界的时候只要容量总数大于等于牛总数就一定可行。但是事实上是如果图不连通，这个方案是不可行的。

质疑了4份SAP模板有问题，最后是自己打开方式不对- -！！模板还是彻底理解了再用，免得心虚。。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef __int64 lld;
const int MAXN=410;
const int INF = ~0u>>2;
const lld Inf = 100000000000000000;


#define clr(a,b) memset(a,b,sizeof(a))
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)

struct EDGE {
    int u,v,c,next;
    EDGE() {}
    EDGE(int u, int v, int c) : u(u), v(v), c(c) {}
}edge[101000];
int E,head[MAXN];
int gap[MAXN], cur[MAXN], pre[MAXN], dis[MAXN];
void add_edge(int s,int t,int c,int cc = 0)
{
    edge[E].v=t;    edge[E].c=c;
    edge[E].next=head[s];   head[s]=E++;
    edge[E].v=s;    edge[E].c=cc;
    edge[E].next=head[t];   head[t]=E++;
}
int min(int a,int b){return (a==-1||b<a)?b:a;}
int SAP(int s,int t,int n)
{
    memset(gap,0,sizeof(gap));
    memset(dis,0,sizeof(dis));
    int i;
    for(i=0;i<n;i++)cur[i]=head[i];
    int u=pre[s]=s,maxflow=0,aug=-1,v;
    gap[0]=n;
    while(dis[s]<n)
    {
    loop:    for(i=cur[u];i!=-1;i=edge[i].next)
         {
             v=edge[i].v;
             if(edge[i].c>0&&dis[u]==dis[v]+1)
             {
                 aug=min(aug,edge[i].c);
                 pre[v]=u;
                 cur[u]=i;
                 u=v;
                 if(u==t)
                 {
                     for(u=pre[u];v!=s;v=u,u=pre[u])
                     {
                         edge[cur[u]].c-=aug;
                         edge[cur[u]^1].c+=aug;
                     }
                     maxflow+=aug;
                     aug=-1;
                 }
                 goto loop;
             }
         }
         int mindis=n;
         for(i=head[u];i!=-1;i=edge[i].next)
         {
             v=edge[i].v;
             if(edge[i].c>0&&dis[v]<mindis)
             {
                 cur[u]=i;
                 mindis=dis[v];
             }
         }
         if((--gap[dis[u]])==0)break;
         gap[dis[u]=mindis+1]++;
         u=pre[u];
    }
    return maxflow;
}

int n,sum;
EDGE tg[101000];
int tot;
lld gg[MAXN][MAXN];

void gao() {
    lld l = 0, r = Inf - 1;
    lld ans = -1;
    while(l <= r) {
        lld m = (l+r)>>1;
        E = 0;
        REP(i,0,2*n+2) head[i] = -1;
        REP(i,0,tot) add_edge(tg[i].u,tg[i].v,tg[i].c);
        FOR(i,1,n) FOR(j,1,n) {
            if(i == j || gg[i][j] > m) continue;
            add_edge(i,j+n,INF);
        }
        if(SAP(0,2*n+1,2*n+2) == sum) r = m - 1, ans = m;
        else l = m + 1;
    }

    printf("%I64d\n", ans);
}

lld min(lld a, lld b) { return a<b ? a : b; }

int main() {
    int m;
    while(~scanf("%d%d", &n, &m)) {
        int a,b;
        tot = 0;
        sum = 0;
        FOR(i,1,n) {
            scanf("%d%d", &a, &b);
            tg[tot ++] = EDGE(0,i,a);
            tg[tot ++] = EDGE(i+n,2*n+1,b);
            tg[tot ++] = EDGE(i,i+n,INF);
            sum += a;
        }
        FOR(i,1,n) FOR(j,1,n) gg[i][j] = Inf;
        FOR(i,1,n) gg[i][i] = 0;
        lld c;
        while(m--) {
            scanf("%d%d%I64d", &a, &b, &c);
            gg[a][b] = gg[b][a] = min(gg[a][b], c);
        }
        FOR(k,1,n) FOR(i,1,n) FOR(j,1,n)
            gg[i][j] = min(gg[i][j], gg[i][k]+gg[k][j]);
        gao();
    }
    return 0;
}