POJ 2391 floyd+二分+最大流

题意：

有N块田，每块田下雨时可以容纳a[i]头牛，每块田现在有b[i]头牛，给出一些田与田之间的无向路径及距离，问下雨时最少多少时间后所有牛都能到避雨的地方。

题解：

明显又是二分答案。floyd求取两点间最短路

PS：要用long long！！！

一开始我想的是三层的图：

①n个点表示n块田    ②和③各n个点（灭个点i和i'，拆点限制容量）

S连①中的点容量a[i]，表示一开始有a[i]头奶牛在i点

①中的点连②中的i，当且仅当两块田之间的距离小于二分值时

②和③对应点相连，限制流量

③中的点和T连INF的边

这样果断tle了。

后来发现③中的点没有用，直接在②和T之间限流即可，优化后就ac了~

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>

#define N 1000
#define M 140000
#define INF 1LL<<55

using namespace std;

int head[N],to[M],next[M];
__int64 map[N][N],len[M],l,r,mid,sum,num[N],hold[N];
int q[M*10],layer[N];
int n,m,S,T,cnt,tot;

struct PX
{
    __int64 a,b,c;
}px[M];

inline bool cmp(const PX &a,const PX &b)
{
    return a.c<b.c;
}

inline void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            r=max(r,map[i][j]);
}

inline void add(int u,int v,__int64 w)
{
    to[cnt]=v; len[cnt]=w; next[cnt]=head[u]; head[u]=cnt++;
    to[cnt]=u; len[cnt]=0; next[cnt]=head[v]; head[v]=cnt++;
}

inline void read()
{
    memset(head,-1,sizeof head); cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            map[i][j]=INF;
        map[i][i]=0;
    }
    r=0; S=0; T=n+n+1;
    for(int i=1;i<=n;i++)
    {
        scanf("%I64d%I64d",&num[i],&hold[i]);
        sum+=num[i];
    }
    __int64 c;
    for(int i=1,a,b;i<=m;i++)
    {
        scanf("%d%d%I64d",&a,&b,&c);
        map[a][b]=map[b][a]=min(c,map[a][b]);
    }
    floyd();
    tot=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            px[++tot].a=i,px[tot].b=j,px[tot].c=map[i][j];
    sort(px+1,px+1+tot,cmp);
}

inline void build()
{
    memset(head,-1,sizeof head); cnt=0;
    for(int i=1;i<=tot;i++)
    {
        if(px[i].c>mid) break;
        add(px[i].a,px[i].b+n,INF);
    }
    for(int i=1;i<=n;i++)
    {
        add(i+n,T,hold[i]);
        add(S,i,num[i]);
    }
}

inline bool bfs()
{
    memset(layer,-1,sizeof layer);
    int h=1,t=2,sta;
    q[1]=S; layer[S]=0;
    while(h<t)
    {
        sta=q[h++];
        for(int i=head[sta];~i;i=next[i])
            if(len[i]&&layer[to[i]]<0)
            {
                layer[to[i]]=layer[sta]+1;
                q[t++]=to[i];
            }
    }
    return layer[T]!=-1;
}

inline __int64 find(int u,__int64 cur_flow)
{
    if(u==T) return cur_flow;
    __int64 res=0,tmp;
    for(int i=head[u];~i&&res<cur_flow;i=next[i])
        if(len[i]&&layer[to[i]]==layer[u]+1)
        {
            tmp=find(to[i],min(cur_flow-res,len[i]));
            len[i]-=tmp; len[i^1]+=tmp; res+=tmp;
        }
    if(!res) layer[u]=-1;
    return res;
}

__int64 dinic()
{
    __int64 ans=0;
    while(bfs()) ans+=find(S,INF);
    return ans;
}

inline void go()
{
    l=0; 
    __int64 ans=-1;
    r+=1000;
    while(l<=r)
    {
        mid=(l+r)>>1;
        build();
        if(dinic()==sum) ans=mid,r=mid-1;
        else l=mid+1;
    }
    if(ans>=INF) puts("-1");
    else printf("%I64d\n",ans);
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF) read(),go();
    return 0;
}