本文主要是介绍poj 2391 Ombrophobic Bovines （网络流），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这是一道很经典的网络流的题目。首先我们考虑假如我们的时间为无穷大。我们吧每个点拆成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 100010
using 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;
}
这篇关于poj 2391 Ombrophobic Bovines （网络流）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
