这是一道很经典的网络流的题目。首先我们考虑假如我们的时间为无穷大。我们吧每个点拆成2个点 i和i’ .。虚拟源点s和汇点t。对于每个点建边(s,i, a[i]) （i‘,t,ib[i]） 。 其中a[i]为给点有多少牛，b[i]为容量。i和j连通 建边 (i，j’,inf);如果最大流==所有牛的个数，就可能装下所有的牛。那么现在我们考虑时间。假设最大时间为T.那么如果i到j的的最短时间>T，，那么i的牛不可能达到j 。于是我们只用建立哪些在T时间内能到达的边。 所以总体思路就是2分时间，然后跑网络流。 这里为什么要拆点，如果不拆点会导致流量的传递，本来不在T时间内到的的也可能传递过去，不需要拆点。 还有一个主意额地方，这题用dinic()可能时间卡的比较紧，我目前还是用isap过的额，dinic一直Tle。
VIEW CODE
//#pragma comment(linker, "/STACK:102400000,102400000")#include<cstdio>#include<cmath>#include<queue>#include<stack>#include<string>#include<cstring>#include<iostream>#include<map>#include<vector>#include<algorithm>#include<stdlib.h>#include<set>#include<ctime>#include<cmath>#define eps 1e-8#define ex 2.7182818284590452354#define pi acos(-1.0)#define inf 0x3fffffff#define DC(n) printf("Case #%d:",++n)#define SD(n) scanf("%d",&n)#define SS(str) scanf("%s",str)#define SDB(n) scanf("%lf",&n)#define ll __int64#define mm 1000000007#define mmax 100010using namespace std;const ll INF=0x3fffffffffffffff;struct edges{int en;int cost;int next;}edge[10000];int point[300][2];int p1[300];int num1;void init1(){memset(p1,-1,sizeof p1);num1=0;}void add1(int st,int en,int cost){edge[num1].en=en;edge[num1].cost=cost;edge[num1].next=p1[st];p1[st]=num1++;}int n,m;struct node{int en,val;int next;}E[100010];int p[500];int num;void init(){memset(p,-1,sizeof p);num=0;}void add(int st,int en,int val){E[num].en=en;E[num].val=val;E[num].next=p[st];p[st]=num++;E[num].en=st;E[num].val=0;E[num].next=p[en];p[en]=num++;}ll dis[210];bool vis[510];int q[510];int cntq;ll cost[210][210];void spfa(int st){for(int i=1;i<=n;i++){dis[i]=INF;vis[i]=0;}cntq=0;q[++cntq]=st;vis[st]=1;dis[st]=0;while(cntq){int x=q[cntq];cntq–;vis[x]=0;for(int i=p1[x];i+1;i=edge[i].next){int v=edge[i].en;ll val=edge[i].cost;if(dis[v]>dis[x]+val){dis[v]=dis[x]+val;if(!vis[v]){vis[v]=1;q[++cntq]=v;}}}}for(int i=1;i<=n;i++)cost[st][i]=dis[i];}void build(ll max_time){init();for(int i=1;i<=n;i++){add(i,i+n,point[i][1]);add(0,i,point[i][0]);add(i+n,2*n+1,point[i][1]);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i!=j){if(cost[i][j]<=max_time)add(i,j+n,inf);}}}}int h[510];int vh[510];int find(int u,int st,int en,int F){if(u==en)return F;int left=F;int tmp=en;for(int i=p[u];i+1;i=E[i].next){int v=E[i].en;int val=E[i].val;if(val>0){if(h[v]+1==h[u]){int d=min(left,val);d=find(v,st,en,d);left-=d;E[i].val-=d;E[i^1].val+=d;if(h[st]>=en+1)return F-left;if(!left)break;}if(h[v]<tmp)tmp=h[v];}}if(left==F){vh[ h[u] ]–;if(vh[h[u] ]==0)h[st]=en+1;h[u]=tmp+1;vh[ h[u] ]++;}return F-left;}int isap(int st,int en){memset(vh,0,sizeof vh);memset(h,0,sizeof h);int ans=0;vh[0]=en+1;while(h[st]<=en)ans+=find(st,st,en,inf);return ans;}int main(){while(scanf("%d %d",&n,&m)!=EOF){int sum=0;ll times=0;init1();for(int i=1;i<=n;i++){scanf("%d %d",&point[i][0],&point[i][1]);sum+=point[i][0];}for(int i=1;i<=m;i++){int st,en,val;scanf("%d %d %d",&st,&en,&val);add1(st,en,val);add1(en,st,val);times+=val;}for(int i=1;i<=n;i++)spfa(i);ll st=0,en=times+1;while(st<en){ll mid=(st+en)>>1;build(mid);int tmp=isap(0,2*n+1);if(tmp==sum)en=mid;elsest=mid+1;}if(en==times+1)printf("-1\n");elseprintf("%I64d\n",(st+en)/2);}return 0;}
含泪播种的人一定能含笑收获。
