POJ 2391 Ombrophobic Bovines

2019-11-14 12:07:46

字體：大中小

來源：轉載

供稿：網友

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; } }