POJ 2391 Ombrophobic Bovines

2019-11-14 12:07:17

字体：大中小

来源：转载

供稿：网友

POJ 2391 Ombrophobic Bovines

网络流

传送门：POJ

题意

F个牛棚，P条路。每个牛棚有初始牛数，能容纳的最大牛数。下雨了，牛要避雨。每个牛棚不能超过容纳数上限。牛棚之间有路，路上没有通过牛的数目限制。问牛走的最远距离最小是多少。无解输出-1。

思路

关于拆点%%%

这题根poj2112很像，同样构图，然后二分。但是有不同。

POJ 2112跟本题很相似，也是二分，但它就没用拆点，本题就用了为啥呢？因为POJ2112上建的图中是一个很明显的二分图，也就是左边的点绝对不会跟左边的点去连边的。而本题中就不一样了，任何点之间都可能有边。会出现这种情况，1->2->3，这是一条链，而1->2最短路为1，2->3为1，1->3为 2，此时如果我们限制最大距离为1的话，建的新图中必然有1->2,2->3, 然后我们就发现问题了，新图中1和3也会间接的连接起来，而我们显然是不想这么让它流的。这就需要拆点了，对每个点x，拆成x’和x”，然后x’和x”之间有一条无限容量的边，这样的话，随便多少牛路过这个点都是可以的。如果i->j这条边符合了距离限制，就加i’->j” 所有的边加完后，建立源点，对所有的x’连边，容量为已经有的牛，汇点的话，就用所有的j”连接汇点，容量就是能容纳的牛的数量。这样一拆点，就发现之前的问题不复存在了，还是比如1->2->3这个例子，加的边是1’->2”，2’->3” 不会有流从1流到3去，因为加的每条边都流向了汇点

代码

注意一下距离需要用longlong存

#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<vector>#include<cmath>#include<queue>using namespace std;const int MAXN=507;const int oo=0x3f3f3f3f;const long long int loo=4223372036854775807ll;typedef long long LL;struct Dinic{ struct Edge{ int from, to, cap, flow;//cap容量 flow流量 Edge(){} Edge(int u, int v, int c, int f){ from=u;to=v;cap=c;flow=f; } }; vector<Edge> edges;//顺序的插入边 vector<int> G[MAXN];//保存边号 bool vis[MAXN];//BFS使用 int d[MAXN]; int cur[MAXN]; void init(int n) { memset(d, 0, sizeof(d)); for(int i=0;i<n;i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0));//单向边第三个参数写0，双向边写cap int t_m=edges.size(); G[from].push_back(t_m-2); G[to].push_back(t_m-1); } bool BFS(int s, int t) { memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(s); d[s]=0; vis[s]=1; while(!Q.empty()) { int x=Q.front();Q.pop(); for(int i=0;i<G[x].size();i++) { Edge& e=edges[G[x][i]]; if(!vis[e.to]&&e.cap>e.flow)//残量网络 { vis[e.to]=1; d[e.to]=d[x]+1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a, int s, int t) { if(x==t||a==0) return a; int flow=0, _f; for(int& i=cur[x];i<G[x].size();i++) { Edge& e=edges[G[x][i]]; if(d[x]+1==d[e.to]&&(_f=DFS(e.to, min(a, e.cap-e.flow), s, t))>0) { e.flow+=_f; edges[G[x][i]^1].flow-=_f; flow+=_f; a-=_f; if(a==0) break; } } return flow; } int Maxflow(int s, int t) { int flow=0; while(BFS(s, t)) { memset(cur, 0, sizeof(cur)); flow+=DFS(s, oo, s, t); } return flow; }};LL ddd[MAXN][MAXN];Dinic dinic;int main(){ int f, p; while(cin>>f>>p) { vector<int> cow1; vector<int> cow2; int should_flow=0; for(int i=1;i<=f;i++) { int t1, t2; scanf("%d%d", &t1, &t2); cow1.push_back(t1); cow2.push_back(t2); ddd[i][i]=0; should_flow+=t1; } memset(ddd, 0x3f, sizeof(ddd)); for(int i=0;i<p;i++) { LL t1, t2, t3; scanf("%lld%lld%lld", &t1, &t2, &t3); ddd[t2][t1]=ddd[t1][t2]=min(t3, ddd[t1][t2]); } for(int k=1;k<=f;k++) { for(int i=1;i<=f;i++) { for(int j=1;j<=f;j++) { if(i==j) continue; ddd[i][j]=min(ddd[i][k]+ddd[k][j], ddd[i][j]); } } } LL l=0, r=loo, res=-1; while(l<=r) { LL mid=(l+r)/2; dinic.init(500); const int sup_t=451, sup_s=450; for(int i=0;i<cow1.size();i++) { dinic.AddEdge(sup_s, i+1, cow1[i]); } for(int i=0;i<cow2.size();i++) { dinic.AddEdge(i+1+205, sup_t, cow2[i]); } for(int i=1;i<=f;i++) { dinic.AddEdge(i, i+205, oo); } for(int i=1;i<=f;i++) { for(int j=1;j<=f;j++) { if(ddd[i][j]<=mid) { dinic.AddEdge(i, j+205, oo); } } } if(dinic.Maxflow(sup_s, sup_t)==should_flow) { res=mid; r=mid-1; } else { l=mid+1; } } PRintf("%lld/n", res); } //system("pause"); return 0;}

上一篇：OpenCV Mat类详解

下一篇：P1042 乒乓球