Floyd+二分+最大流（dinic）+拆点 貌似这样子显得很高端呢
给定一个无向图，点 i 处有 Ai 头牛，点 i 处的牛棚能容纳 Bi 头牛，求一个最短时 间 T 使得在 T 时间内所有的牛都能进到某一牛棚里去。（1 <= N <= 200, 1 <= M <= 1500, 0 <= Ai <= 1000, 0 <= Bi <= 1000, 1 <= Dij <= 1,000,000,000） 这个数据范围总归是要开long long了，据说很多人wa在这
将每个点 i 拆成两个点 i’, i”，连边(s, i’, Ai), (i”, t, Bi)。二分最短时间 T，若 d[i][j]<=T （d[i][j]表示点 i, j 之间的最短距离）则加边(I’, j”, ∞)。每次根据最大流调整二分 的上下界即可。
最开始的时候我是没有想到拆点的，只是随手画了个图，不小心画成了两份，二分图做多了QAQ，然后纠结如果1到3的最短路是1-2 2-3怎么办，这个图不能往回走流量啊，然后想到了求出所有的最短路再说，这就是floyd
然后开始思考流量怎么给，首先s到每个点是整个草原上多少猪，每个点到t是每个草原的 shelter能装下多少猪，如果猪多了，肯定要送到别的草原上，这个时候，怎么改这个图呢，如果直接连边，1-2，2-3，那么相当于1-3也可以直接走，而这样是不对的，1-3可以走也是咱们之前floyd求过的再放进去，为什么不对？ 因为后面的做法是二分，你可以朴素的找，实测会tle23333 为什么可以二分？ 单调性不用说，最大值一定不会超过floyd之后最长的时间，因为所有猪是一起走的，所以上下界ok，找的时候，找到=猪的总数也不能退出，因为要找到最短的时间，只能不断更新ans，直到退出循环
知道了要二分之后，就可以说明为什么不拆点不行了，每次二分要重新建图，把dis<=mid的加进去，mid = 3,1-2 时间为 2 , 2-3 为2的话，现在的图1 3连通，但是时间为4 > mid，所以是不能走的，如此，就说明了。。。
最后，每次重新建图，tot = 0，memset（head，-1，。。。）即可
#include <cstdio> #include <iostream> #include <cstring> #include <queue> using namespace std; int F,P,S,T; #define INF1 0x7FFFFFFF #define INF 0x7FFFFFFFFFFFFFFF const int maxn = 410; int head[maxn], level[maxn],au[maxn],bv[maxn],ANS,q[maxn]; long long dis[maxn][maxn],tot; struct node{ int v,c,next; }edges[100010]; int bfs(){ int f = 0, t = 1; q[0] = S; memset(level,-1,sizeof(level)); level[S] = 0; while(f<t){ int u = q[f++]; for(int k = head[u];k != -1 ;k = edges[k].next){ int v = edges[k].v; int cap = edges[k].c; if(cap > 0 && level[v] == -1){ level[v] = level[u]+1; q[t++] = v; } } } return level[T] != -1; } int dfs(int s,int c){ if(s == T) return c; int temp; for(int k = head[s];k!=-1;k = edges[k].next){ int v = edges[k].v; int cap = edges[k].c; if(cap > 0 && level[v] == level[s]+1 && (temp = dfs(v,min(cap,c)))>0){ edges[k].c -= temp; edges[k^1].c += temp; return temp; } } level[s] = -1; return 0; } int dinic(){ int maxflow = 0,flow; while(bfs()){ while(flow = dfs(S,INF1)) maxflow += flow; } return maxflow; } void floyd(){ for(int i = 1 ; i <= F ; i++){ for(int j = 1; j <= F ;j++){ for(int k = 1; k <= F ;k++){ if(dis[j][i]!=INF&&dis[i][k]!=INF &&i != k &&j!=k) if(dis[j][i]+dis[i][k] < dis[j][k]){ dis[j][k] = dis[j][i]+dis[i][k]; } } } } } void add(int u,int v,int c){ edges[tot].v = v;edges[tot].c = c;edges[tot].next = head[u];head[u] = tot++; edges[tot].v = u;edges[tot].c = 0;edges[tot].next = head[v];head[v] = tot++; } void init(){ ANS = 0; for(int i = 1 ; i <= F ;i++) for(int j = 1; j <= F ;j++) if(i!=j) dis[i][j] = INF; else dis[i][j] = 0; for(int i = 1 ; i <= F ;i++){ scanf("%d%d",&au[i],&bv[i]); ANS += au[i]; } for(int i = 0 ; i < P;i++){ long long u,v,di; scanf("%I64d%I64d%I64d",&u,&v,&di); dis[u][v] = min(di,dis[u][v]); dis[v][u] = min(di,dis[v][u]); } floyd(); } void sov(){ long long left = 0,right = 0,ans = -1; for(int i = 1 ; i <= F ;i++) for(int j = 1; j <= F ;j++) if(dis[i][j] != INF) right = max(right,dis[i][j]); while(left <= right){ long long mid = left+(right-left)/2; // cout <<"mod = "<< mid <<endl; tot = 0; memset(head,-1,sizeof(head)); for(int i = 1; i <= F ;i++){ add(i*2,i*2+1,INF1); add(S,i*2,au[i]); add(i*2+1,T,bv[i]); } //cout <<mid <<endl; for(int i = 1; i <= F ;i++) for(int j = 1 ; j <= F ;j++) if(dis[i][j] <= mid&&i!=j) add(i*2,j*2+1,INF1); long long maxflow = dinic(); // cout << maxflow<<endl; if(maxflow == ANS){ ans = mid; right = mid-1; } else left = mid+1; } printf("%I64d\n",ans); } int main(){ while(~scanf("%d%d",&F,&P)){ S = 1; T = 2*(F+1); init(); sov(); } } /* 6 6 10 0 0 3 0 7 3 0 0 2 0 1 1 2 120 5 2 80 5 1 20 5 6 30 6 1 110 4 3 30 */