联系：http://poj.org/problem?id=2391
题意：有f个草场，每一个草场当前有一定数目的牛在吃草，下雨时它能够让一定数量的牛在这里避雨，f个草场间有m条路连接，每头牛通过一条路从一点到还有一点有一定的时间花费，如今要下雨了，农场主发出警报牛就会马上去避雨。
如今告诉每一个草场的情况。以及m条边的信息。农场主至少须要提前多久发出警报才干保证全部牛都能避雨？假设不是全部牛都能成功避雨输出-1。
思路：这道题须要拆点，是看到魏神的博客才知道的。我们把原图拆成一个二分图，避免突破最大距离限制的情况，每一个点变成两个点，即i变为i‘和i’‘，建立一个源点连接每一个i’，容量为初始每一个草场牛的数目。建立一个汇点，全部的i‘’指向汇点，容量为每一个草场能容纳的牛的数目。假设两个点i和j连接。则在i’和j‘’以及j‘和i’‘之间建一条路径。容量为INF，能够走无限多的牛。然后这道题就和之前做的一道POJ2112一样了，POJ2112不用拆点，由于它本身就是一个二分图。
接下来就是Floyd处理出随意两点间最短路径。然后二分答案。
可是这道题还没有完，我套之前的Dinic模板，TLE了。这道题最大可能的边数比POJ2112大，而Case时限一样，我手写队列。还是TLE，我再把vis数组去掉用dist取代vis功能，还是TLE，我在网上搜AC的Dinic代码，看到一个和我的差点儿相同。粘贴交了一发。TLE，无力吐槽。。。
找到了一个看上去有些修改的代码，依照它修改的地方改我自己的。219MS AC。
我看了一下。我认为基本的优化地方是这样：
1. 我之前的模板，是从源点起找遍每一条增广路进行松弛，优化算法是找到一条增广路松弛、退出，更新最大流值，再找下一条，直到更新值返回0说明已更新到头，避免了多余的搜索。
2. 假设此时的顶点已不存在增广路，将它从当前的层次网络中删除。回溯后不会再搜。
我认为这是两个优化到的地方，这么进行了优化之后效率提升非常明显！
#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 200100
#define eps 1e-7
#define INF 0x7FFFFFFF
#define LLINF 0x7FFFFFFFFFFFFFFF
#define seed 131
#define mod 1000000007
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1struct node{int u,w,next;
}edge[100010];
int head[410],dist[410],q[410];
int aa[410],bb[410];
ll e[410][410];
int n,m,cnt,src,sink,f,p;
void add_edge(int a,int b,int c){edge[cnt].u = b;edge[cnt].w = c;edge[cnt].next = head[a];head[a] = cnt++;
}
void floyd(){int i,j,k;for(k=1;k<=f;k++){for(i=1;i<=f;i++){if(e[i][k]==LLINF) continue;for(j=1;j<=f;j++){if(e[i][k]+e[k][j]<e[i][j]&&e[i][k]!=LLINF&&e[k][j]!=LLINF)e[i][j] = e[i][k] + e[k][j];}}}
}
void build_graph(ll minm){int i,j;cnt = 0;memset(head,-1,sizeof(head));for(i=1;i<=f;i++){add_edge(src,i,aa[i]);add_edge(i,src,0);add_edge(i+f,sink,bb[i]);add_edge(sink,i+f,0);for(j=1;j<=f;j++){if(e[i][j]<=minm){add_edge(i,j+f,INF);add_edge(j+f,i,0);}}}
}
bool bfs(){int i,j;memset(dist,-1,sizeof(dist));int f = 0, t = 1;q[0] = src;dist[src] = 1;while(f<t){int u = q[f++];for(i=head[u];i!=-1;i=edge[i].next){int v = edge[i].u;if(dist[v]==-1&&edge[i].w){dist[v] = dist[u] + 1;q[t++] = v;}}}if(dist[sink]!=-1) return true;return false;
}
int dfs(int u,int delta){int i,j;int dd;if(u==sink) return delta;for(i=head[u];i!=-1;i=edge[i].next){if(dist[edge[i].u]==dist[u]+1&&edge[i].w&&(dd = dfs(edge[i].u,min(delta,edge[i].w)))){edge[i].w -= dd;edge[i^1].w += dd;return dd;}}dist[u] = -1;return 0;
}
int main(){int i,j;int ta,tb,tc;int cow;scanf("%d%d",&f,&p);n = 2 * f + 2;src = 0;sink = 2 * f + 1;cow = 0;for(i=1;i<=f;i++){scanf("%d%d",&aa[i],&bb[i]);cow += aa[i];}for(i=0;i<=f;i++){for(j=0;j<=f;j++)e[i][j] = LLINF;e[i][i] = 0;}for(i=0;i<p;i++){scanf("%d%d%d",&ta,&tb,&tc);if(tc<e[ta][tb]) e[ta][tb] = e[tb][ta] = tc;}floyd();ll mid,l = 0,r = 0;for(i=1;i<=f;i++){for(j=1;j<=f;j++){if(e[i][j]!=LLINF) r = max(e[i][j],r);}}int sum;ll ans = -1;while(l<=r){mid = (l+r)>>1LL;//cout<<l<<" "<<r<<endl;sum = 0;build_graph(mid);while(bfs()){while(1){int ttt = dfs(src,INF);if(!ttt) break;sum += ttt;}}if(sum==cow){ans = mid;r = mid-1;}else l = mid + 1;}printf("%I64d\n",ans);return 0;
}版权声明：本文博主原创文章。博客，未经同意不得转载。
