同poj 2112.
代码：
//poj 2391//sep9#include <iostream>#include <queue>#include <algorithm>using namespace std;typedef long long ll;const int maxN=1024;const int maxM=100002;const ll MAX=(1ULL<<63)-1; struct Edge{int v,f,nxt;}e[maxM*2+10];queue<int> que;int src,sink;int g[maxN+10];int nume;bool vis[maxN+10];int dist[maxN+10];ll d[maxN][maxN];int in[maxN],out[maxN];int f,p,sum; void addedge(int u,int v,int c){e[++nume].v=v;e[nume].f=c;e[nume].nxt=g[u];g[u]=nume;e[++nume].v=u;e[nume].f=0;e[nume].nxt=g[v];g[v]=nume;}void init(){memset(g,0,sizeof(g));nume=1;}int bfs(){while(!que.empty()) que.pop();memset(dist,0,sizeof(dist));memset(vis,0,sizeof(vis));vis[src]=true;que.push(src);while(!que.empty()){int u=que.front();que.pop();for(int i=g[u];i;i=e[i].nxt)if(e[i].f&&!vis[e[i].v]){que.push(e[i].v);dist[e[i].v]=dist[u]+1;vis[e[i].v]=true;if(e[i].v==sink)return 1;}}return 0;}int dfs(int u,int delta){if(u==sink)return delta;int ret=0;for(int i=g[u];ret<delta&&i;i=e[i].nxt)if(e[i].f&&dist[e[i].v]==dist[u]+1){int dd=dfs(e[i].v,min(e[i].f,delta-ret));if(dd>0){e[i].f-=dd;e[i^1].f+=dd;ret+=dd;}elsedist[e[i].v]=-1;}return ret;}int dinic(){int ret=0;while(bfs()==1)ret+=dfs(src,INT_MAX);return ret;}bool work(ll max_len){init();src=0,sink=2*f+1;for(int i=1;i<=f;++i)addedge(src,i,in[i]);for(int i=1;i<=f;++i)for(int j=1;j<=f;++j)if(d[i][j]<=max_len)addedge(i,j+f,INT_MAX);for(int j=f+1;j<=2*f;++j)addedge(j,sink,out[j-f]);if(dinic()==sum)return true;return false;}int main(){scanf("%d%d",&f,&p);for(int i=1;i<=f;++i){for(int j=1;j<=f;++j)d[i][j]=d[j][i]=MAX;d[i][i]=0;}sum=0;for(int i=1;i<=f;++i){scanf("%d%d",&in[i],&out[i]);sum+=in[i];}while(p–){int a,b;ll c;scanf("%d%d%I64d",&a,&b,&c);c=min(d[a][b],c);d[a][b]=d[b][a]=c;}for(int k=1;k<=f;++k)for(int i=1;i<=f;++i)for(int j=1;j<=f;++j)if(d[i][k]!=MAX&&d[k][j]!=MAX)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);ll l=0,r=MAX/2,mid,ans=-1;while(l<r){mid=(l+r)/2;if(work(mid)){ans=mid;r=mid;}elsel=mid+1;}printf("%I64d",ans);return 0;}
，旅行，不要害怕错过什么，
