[P2402] 奶牛隐藏

二分答案+最大流。

对答案建图，若长度≤答案，连边即可。（先要预处理点对间的最短路）
当然得拆点，（否则，就此题而言，就会出现流量x-y不走x-y的最短路边的情况，而是走了一条路径 ，答案约束的仅仅是路径上的边长的最大值，而非总和）

流量：s - 某点入点 - 某点出点 - t

另外，由于此题卡实现，考虑二分边权集合，就酱

---

吐槽 第一次建图时“因为一头牛经过边(x,y,c)用时为c，所以对于时限t来说，这条边的容量为t/c。 ”woc我在想什么。。

#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int n=4e2+7;
const int l=2e6+7;
const int inf=0x3f3f3f3f3f3f3f3f;

int s=n-1,t=n-2;
int head[n],to[l],upp[l],last[l],cnt=1;
int que[n],lev[n],hd,tl;

inline void add_edge(int x,int y,int u1,int u2=0) {
    to[++cnt]=y,upp[cnt]=u1,last[cnt]=head[x],head[x]=cnt;
    to[++cnt]=x,upp[cnt]=u2,last[cnt]=head[y],head[y]=cnt; 
}
inline bool bfs() {
    memset(lev,0,sizeof lev);
    lev[s]=1;
    que[hd=0,tl=1]=s;
    while(hd<tl) {
        int x=que[++hd];
        for(int i=head[x]; i; i=last[i]) if(upp[i]>0 && !lev[to[i]]) 
            lev[to[i]]=lev[x]+1, que[++tl]=to[i];
    }
    return lev[t]!=0;
}
int dfs(int x,int tf) {
    if(x==t) return tf;
    int tot=0,tmp;
    for(int i=head[x]; i; i=last[i]) if(upp[i]>0 && lev[x]+1==lev[to[i]]) {
        tmp=dfs(to[i],min(tf-tot,upp[i]));
        if(tmp) upp[i]-=tmp,upp[i^1]+=tmp,tot+=tmp;
        if(tot==tf) break;
    }
    if(!tot) lev[x]=-1;
    return tot;
}

int n,m,sum;
int s[210],p[210],dis[210][210];

struct edge {
    int x,y,w;
    bool operator<(const edge&d) const {
        return w<d.w;
    }
} c[40010];
int d[40010];

inline bool check(int lmt) {
    cnt=1;
    memset(head,0,sizeof head);
    for(int i=1; i<=n; ++i) {
        add_edge(s,i,s[i]);
        add_edge(n+i,t,p[i]);
    }
    for(int i=1; c[i].w<=lmt && i<=m; ++i) {
        add_edge(c[i].x,n+c[i].y,inf);
        add_edge(c[i].y,n+c[i].x,inf);
    }
    int tot=0;
    while(bfs()) tot+=dfs(s,inf);
    return tot>=sum;
}

signed main() {
    scanf("%lld%lld",&n,&m);
    memset(dis,0x3f,sizeof dis);
    for(int i=1; i<=n; ++i) {
        scanf("%lld%lld",s+i,p+i);
        dis[i][i]=0;
        sum+=s[i]; 
    }
    for(int i=1,x,y,w; i<=m; ++i) {
        scanf("%lld%lld%lld",&x,&y,&w);
        if(dis[x][y]>w) {
            dis[x][y]=w;
            dis[y][x]=w;
        }
    }
    for(int k=1; k<=n; ++k) {
        for(int i=1; i<=n; ++i) {
            for(int j=1; j<=n; ++j) {
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }       
        }
    } 
    m=0;
    for(int i=1; i<=n; ++i) {
        for(int j=i; j<=n; ++j) {
            if(dis[i][j]<inf) c[++m]=(edge){i,j,dis[i][j]};
        }
    }
    sort(c+1,c+m+1);
    int l=1,r=0,mid,ans=-1;
    for(int i=1; i<=m; ++i) {
        if(c[i].w!=c[i-1].w) d[++r]=c[i].w;
    }
    while(l<=r) {
        mid=(l+r)>>1;
        if(check(d[mid])) ans=d[mid],r=mid-1;
        else l=mid+1;
    }
    printf("%lld\n",ans);
    return 0;
}