题目大意：F个草场，P条道路（无向），每个草场初始有几头牛，还有庇护所，庇护所有个容量，每条道路走完都有时间，问所有奶牛都到庇护所最大时间最小是多少？

思路：和POJ2112一样的思路，二分以后构建网络流跑就行TUT，问题是，这题是无向边！！无向边啊 题目还给出

3 2 70
2 3 90
这么让人觉得是有向边的数据，纠结过这个之后再把数组开小点（开打了会TLE ）然后就能AC了

#include <stdio.h>#include <iostream>#include <string.h>#include <algorithm>#include <queue>#define maxn 100009#define esp 0.001#define inf 0x3f3f3f3fusing namespace std;long long head[maxn],next[maxn],point[maxn],flow[maxn];long long append[maxn];long long dist[maxn],dis[300][300],now=0,full=0,cow[maxn],shelter[maxn];long long cop[maxn];inline void add(long long x,long long y,long long u,long long v){    next[++now]=head[x];    head[x]=now;    point[now]=y;    flow[now]=u;    append[now]=v;    next[++now]=head[y];    head[y]=now;    point[now]=x;    flow[now]=0;    append[now]=v;}int bfs(long long s,long long t,long long x){    queue<long long>q;    q.push(s);    memset(dist,-1,sizeof(dist));    dist[s]=0;    while(!q.empty())    {        int u=q.front();        q.pop();        for(int i=head[u];i;i=next[i])        {            int k=point[i];            if(dist[k]==-1 && flow[i] &&append[i]<=x)            {                dist[k]=dist[u]+1;                q.push(k);            }        }    }    return dist[t]!=-1;}int dfs(long long s,long long d,long long t,long long x){    if(s==t)return d;    long long res=0;    for(int i=head[s];i&&res<d;i=next[i])    {        int u=point[i];        if(dist[u]==dist[s]+1 &&flow[i] && append[i]<=x)        {            int dd=dfs(u,min(flow[i],d-res),t,x);            if(dd)            {                flow[i]-=dd;                flow[((i-1)^1)+1]+=dd;                res+=dd;            }        }    }    if(!res)dist[s]=-1;    return res;}int judge(long long x,int s,int t){    long long ans=0;    while(bfs(s,t,x))    ans+=dfs(s,inf,t,x);    memcpy(flow,cop,sizeof(flow));    if(ans==full)return 1;else return 0;}int main(){    long long n,m,x,y,v;    long long l=0,r=0;    memset(dis,-1,sizeof(dis));    scanf("%I64d%I64d",&n,&m);    for(int i=1;i<=n;i++)    {        scanf("%I64d%I64d",&cow[i],&shelter[i]);        full+=cow[i];    }    for(int i=1;i<=m;i++)    {        scanf("%I64d%I64d%I64d",&x,&y,&v);        if(dis[x][y]==-1)dis[x][y]=dis[y][x]=v;        else dis[x][y]=dis[y][x]=min(dis[x][y],(long long)v);        r=max(r,dis[x][y]);    }    long long s=2*n+10,t=2*n+11;    for(int i=1;i<=n;i++)add(s,i,cow[i],0);    for(int i=1;i<=n;i++)add(n+1+i,t,shelter[i],0);    for(int i=1;i<=n;i++)add(i,i+n+1,inf,0);    for(int k=1;k<=n;k++)    {        for(int i=1;i<=n;i++)if(i!=k)        {            for(int j=1;j<=n;j++)if(j!=k &&j!=i &&dis[i][k]!=-1&&dis[k][j]!=-1)            {                dis[i][j]=(dis[i][j]==-1)?dis[i][k]+dis[k][j]:                min(dis[i][j],dis[i][k]+dis[k][j]);                r=max(dis[i][j],r);            }        }    }    for(int i=1;i<=n;i++)    {        for(int j=1;j<=n;j++)        {            if(dis[i][j]!=-1)            {                add(i,j+1+n,inf,dis[i][j]);                //printf("%d %I64d %I64d\n",i,j,dis[i][j]);            }        }    }    memcpy(cop,flow,sizeof(flow));    long long temp=++r;    while (l<r)    {        long long mid=(l+r)>>1;        if(judge(mid,s,t)==1)r=mid;else l=mid+1;    }    if(r==temp)printf("-1\n");else    printf("%I64d\n",r);    return 0;}

POJ 2391 Ombrophobic Bovines【二分 网络流】