poj2391：http://poj.org/problem?id=2391
题意：一个人有n个农场，每个农场都一个避雨的地方，每个农场有一些牛，每个避雨的地方能容纳牛的数量是有限的。农场之间有一些道路可以连通。现在给出每个农场的牛的数量以及每个避雨点的值，问你所有的牛都找到一个避雨点的时间最短是多少。
题解：本题个人认为对于初学者来说，比较难了。看了别人的题解，本题的考察的知识点有：Floyd+二分+网络最大流，以及图论里面的拆点和建图。首先：对于所有的牛来说，如果农场是连通的，则最短的时间最坏的情况是任意两点之间距离的最大值所以要用Floyd来求n源最短路。然后最初最大的那个值。第二：建图，超级源点0，会点2*n+1，然后拆点，把那个农场拆成2*n个点，
例如：4个点的话
1 5
2 6
3 7
4 8
然后建边，以上的点，左边的点与0点建边，边权的容量为每个农改现在的牛的数量，右边的点与会点建边，边的容量为每个避雨点的容量。然后1和5之间，2和6之间建边，边权INF，然后二分答案（就是刚才的那个最大数值），对于任意的两点之间，如果两点之间的距离小于这个最大值，说明可以由i这个点牛向j移动所以i和j+n之间要建边，边权INF
每一二分答案，跑最大流，如果最大流等于牛的总数，说明这个距离满足条件，继续缩小距离再跑，知道不行就停止，则此时的距离就是最短的距离，保证所有牛都能找到避雨点的距离。
注意：本题的数据，距离会爆出int
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int INF=;
const int MAXN=;
const long long INFs=100000000000000LL;
int val1[MAXN],val2[MAXN];
struct Node{
int f;
int c;
};
long long dist[MAXN][MAXN];//求最短路
int pre[MAXN];//网络流的分层
Node map[MAXN][MAXN];//网络流的图
int n,m;
int se,sx;//会点和源点
bool BFS(){//层次网络
memset(pre,,sizeof(pre));
queue<int>Q;
Q.push();
pre[]=;
while(!Q.empty()){
int v=Q.front();
Q.pop();
for(int i=;i<=*n+;i++)
if(!pre[i]&&map[v][i].c-map[v][i].f){
pre[i]=pre[v]+;
Q.push(i);
}
}
return pre[se]!=;
}
int dinic(int pos,int flow){//网路流
int f=flow;
if(pos==se)
return flow;
for(int i=;i<=*n+;i++){
if(map[pos][i].c-map[pos][i].f&&pre[i]==pre[pos]+){
int a=map[pos][i].c-map[pos][i].f;
int temp=dinic(i,min(a,flow));
map[pos][i].f+=temp;
map[i][pos].f-=temp;
flow-=temp;
}
}
return f-flow;
}
int slove(){//总流
int sum=;
while(BFS())
sum+=dinic(sx,INF);
return sum;
}
void build(long long limit){//建图
memset(map,,sizeof(map));
for(int i=;i<=n;i++)
if(val1[i]){
map[][i].c=val1[i];
map[][i].f=;
map[i][i+n].c=INF;
map[i][i+n].f=;
}
for(int i=;i<=n;i++){
if(val2[i]){
map[i+n][*n+].c=val2[i];
map[i+n][*n+].f=;
}
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
if(dist[i][j]<=limit&&i!=j){
map[i][j+n].c=INF;
map[i][j+n].f=;
}
}
}
long long Floyd(){//求n源最短路
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
if(i!=k&&i!=j&&k!=j&&dist[i][k]+dist[k][j]<dist[i][j])
dist[i][j]=dist[i][k]+dist[k][j];
}
long long ans=;//注意这里初始化，因为一下的可能不会执行，可能没有满足条件ans
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(dist[i][j]<INFs&&dist[i][j]>ans)
ans=dist[i][j];
return ans;
}
void init(){//初始化
memset(val1,,sizeof(val1));
memset(val2,,sizeof(val2));
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
dist[i][j]=INFs;
}
int main(){
int c,f,u,v,sum;long long w;
while(~scanf("%d%d",&n,&m)){
init();sum=;sx=;se=*n+;
for(int i=;i<=n;i++){
scanf("%d%d",&f,&c);
val1[i]=f;val2[i]=c;
sum+=f;
}
for(int i=;i<=m;i++){
scanf("%d %d %I64d",&u,&v,&w);
if(w<dist[u][v])
dist[u][v]=dist[v][u]=w;
}
long long r=Floyd(),ans=-,l=;
while(l<=r){//二分答案，不断缩小答案
long long mid=(l+r)/;
build(mid);
if(slove()>=sum){
r=mid-;ans=mid;
}
else
l=mid+;
}
printf("%I64d\n",ans);
}
}