<题目链接>
题目大意：
给定一个有$n$个顶点和$m$条边的无向图，点$i$ 处有$A_i$头牛，点$i$ 处的牛棚能容纳$B_i$头牛，每条边有一个时间花费$t_i$(表示从一个端点走到另一个端点所需要的时间)，求一个最短时间T使得在T时间内所有的牛都能进到某一牛棚里去。$(1 <= N <= 200, 1 <= M <= 1500,0 <= A_i <= 10^3, 0 <= B_i <= 10^3, 1 <= Dij <= 10^9)$。
解题分析：
很明显要二分答案，二分枚举最短的时间，然后用最大流去进行验证。将每个点$i$拆成两个点$i$和$i+n$，然后就是对于每次枚举的答案，进行重新建图，然后跑最大流，如果最大流等于所有牛的数量，则说明所有的牛都有牛棚能够停留，符合条件。建图的方法就是：超级源点向所有的点$i$连一条边，容量为i点初始牛的数量，所有点$i+n$向汇点连一条边，容量为该点牛的容量。因为点的数量很少，floyd预处理出任意两点之间的最短距离，然后对于每次枚举的时间T，最短距离小于等于T的边就加入网络，建好图之后，跑一遍最大流，进行判断。
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std; typedef long long ll;
const int N = ;
const ll INF = 1e18;
int n,m,st,ed;
int num[N],capa[N];
ll g[N][N],fullFlow; template<typename T>
inline void read(T&x){
x=;int f=;char c=getchar();
while(c<'' || c>''){ if(c=='-')f=-;c=getchar(); }
while(c>='' && c<=''){ x=x*+c-'';c=getchar(); }
x*=f;
}
struct Dinic
{
struct edge{ int from,to;ll cap,flow; };
vector<edge>es;
vector<int>G[N];
bool vis[N];
int g[N],iter[N];
void init(int n){
for(int i=; i<=n+; i++)G[i].clear();
es.clear();
}
void addedge(int from,int to,ll cap){
es.push_back((edge){from,to,cap,});
es.push_back((edge){to,from,,});
int x=es.size();
G[from].push_back(x-);
G[to].push_back(x-);
}
bool BFS(int s,int t){
memset(vis,,sizeof(vis));
queue <int> q;
vis[s]=;
g[s]=;
q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=; i<G[u].size(); i++){
edge &e=es[G[u][i]];
if(!vis[e.to]&&e.cap>e.flow){
vis[e.to]=;
g[e.to]=g[u]+;
q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int u,int t,ll f){
if(u==t||f==)return f;
int numflow=,d;
for(int &i=iter[u]; i<G[u].size(); i++){
edge &e=es[G[u][i]];
if(g[u]+==g[e.to]&&(d=DFS(e.to,t,min(f,e.cap-e.flow)))>){
e.flow+=d;
es[G[u][i]^].flow-=d;
numflow+=d;
f-=d;
if(f==)break;
}
}
return numflow;
}
int Maxflow(int s,int t){
int flow=;
while(BFS(s,t)){
memset(iter,,sizeof(iter));
int d=;
while(d=DFS(s,t,INF))flow+=d;
}
return flow;
}
}dinic; bool check(ll T){ //最长的时间限制
dinic.init(N);
for(int i=;i<=n;i++){
dinic.addedge(st,i,num[i]); //源点向每个点连一条边，容量为这个点的牛的数量
dinic.addedge(i+n,ed,capa[i]); //每个点拆点之后的点向汇点连一条边，容量为这个点能够容纳牛的数量
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(g[i][j]<=T) //将符合条件的边加上
dinic.addedge(i,j+n,INF);
return dinic.Maxflow(st,ed) == fullFlow; //判断是否满流，即是否所有的牛都有牛棚住
}
inline void Floyd(){ //floyd求出任意两点之间的最短距离
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(g[i][j]>g[i][k]+g[k][j])
g[i][j]=g[i][k]+g[k][j];
}
inline void Init(){
fullFlow = ;
st=,ed=*n+;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
g[i][j]=(i==j)?:INF; //初始化任意两点之间的距离
for(int i=;i<=n;i++){
read(num[i]);read(capa[i]);
fullFlow +=num[i]; //记录所有牛的数量
}
for(int i=;i<=m;i++){
int u,v;ll w;
read(u);read(v);read(w);
g[u][v]=g[v][u]=min(g[u][v],w);
}
Floyd();
}
int main(){
while(~scanf("%d%d",&n,&m)){
Init();
ll l=,r=;//二分的上下界
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(g[i][j]<INF)
r=max(r,g[i][j]); //找到时间的上界
ll ans=-; //二分答案
while(l<=r){
ll mid=(l+r)>>;
if(check(mid))ans=mid,r=mid-;
else l=mid+;
}
printf("%lld\n",ans);
}
}