有上下界的網(wǎng)絡(luò)流1-無(wú)源匯帶上下界網(wǎng)絡(luò)流SGU194

今天開始啃網(wǎng)絡(luò)流了。對(duì)于求解無(wú)源匯帶上下界的網(wǎng)絡(luò)流，我們可以這樣建圖：
建圖模型：?
????????以前寫的最大流默認(rèn)的下界為0，而這里的下界卻不為0，所以我們要進(jìn)行再構(gòu)造讓每條邊的下界為0，這樣做是為了方便處理。對(duì)于每根管子有一個(gè)上界容量up和一個(gè)下界容量low，我們讓這根管子的容量下界變?yōu)?，上界為up-low。可是這樣做了的話流量就不守恒了，為了再次滿足流量守恒，即每個(gè)節(jié)點(diǎn)"入流=出流”，我們?cè)鲈O(shè)一個(gè)超級(jí)源點(diǎn)st和一個(gè)超級(jí)終點(diǎn)sd。我們開設(shè)一個(gè)數(shù)組du[]來(lái)記錄每個(gè)節(jié)點(diǎn)的流量情況。

du[i]=in[i]（i節(jié)點(diǎn)所有入流下界之和）-out[i]（i節(jié)點(diǎn)所有出流下界之和）。

當(dāng)du[i]大于0的時(shí)候，st到i連一條流量為du[i]的邊。

當(dāng)du[i]小于0的時(shí)候，i到sd連一條流量為-du[i]的邊。

最后對(duì)（st，sd）求一次最大流即可，當(dāng)所有附加邊全部滿流時(shí)，有可行解。
（我們默認(rèn)了圖中每條邊已經(jīng)有了最小的流量，可是現(xiàn)在的圖中的點(diǎn) 入流不等于出流，于是我們通過(guò)附加邊使得：
?????? 1. 超級(jí)源點(diǎn) 連接到 入流大于出流的點(diǎn)，以增大該點(diǎn)的出流，使實(shí)際流量平衡（實(shí)際流量為最小流量+當(dāng)前流量，并且不算超級(jí)源點(diǎn)和匯點(diǎn)的流量）。
?????? 2.出流大于入流的點(diǎn) 連接到 超級(jí)匯點(diǎn)，以增大該點(diǎn)的入流（因?yàn)樵擖c(diǎn)可以把流量全部排到超級(jí)匯點(diǎn)，所以可以有跟多的流量流入該點(diǎn)），使實(shí)際流量平衡。

注意：無(wú)源匯帶上下界的網(wǎng)絡(luò)流中 求出來(lái)的網(wǎng)絡(luò)流是個(gè)循環(huán)體，即雖然沒(méi)有源點(diǎn)匯點(diǎn)但內(nèi)部的點(diǎn)都保持流量守恒。
??????????? 且該算法僅能求出一個(gè)可行解，最終得到的網(wǎng)絡(luò)流并不能保證是最大流。


SGU194題目大意：
給n個(gè)點(diǎn)，及m根pipe，每根pipe用來(lái)流躺液體的，單向的，每時(shí)每刻每根pipe流進(jìn)來(lái)的物質(zhì)要等于流出去的物質(zhì)，要使得m條pipe組成一個(gè)循環(huán)體，里面流躺物質(zhì)。并且滿足每根pipe一定的流量限制，范圍為[Li,Ri].即要滿足每時(shí)刻流進(jìn)來(lái)的不能超過(guò)Ri(最大流問(wèn)題)，同時(shí)最小不能低于Li。
今晚RP不錯(cuò)，一遍就AC。
下面是我的代碼：

1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<algorithm> 5 #include<vector> 6 #include<queue> 7 #include<cstring> 8 #define maxn 0x7fffffff 9 using namespace std; 10 struct edge{int to,cap,rev,num;}; 11 int flow[100000],ch[250],du[250]; 12 vector <edge> E[250]; 13 int st,sd,n,m; 14 void Add_Edge(int from,int to,int cap,int num){ 15 edge t;t.num=num*2; 16 t.to=to,t.cap=cap,t.rev=E[to].size(); 17 E[from].push_back(t); 18 t.num=num*2+1; 19 t.to=from,t.cap=0,t.rev=E[from].size()-1; 20 E[to].push_back(t); 21 } 22 bool bfs(){ 23 queue <int> que; 24 memset(ch,-1,sizeof(ch)); 25 ch[st]=0;que.push(st); 26 while(que.size()){ 27 int t=que.front();que.pop(); 28 for(int i=0;i<E[t].size();i++){ 29 if(E[t][i].cap && ch[E[t][i].to]<0) { 30 ch[E[t][i].to]=ch[t] + 1; 31 que.push(E[t][i].to); 32 } 33 } 34 } 35 return (ch[sd]>-1); 36 } 37 int dfs(int v,int f){ 38 int r=0; 39 if(v==sd) return f; 40 for(int i=0;i<E[v].size();i++){ 41 if(f==0) return r; 42 edge &t=E[v][i]; 43 if(ch[t.to]==ch[v]+1 && t.cap>0) { 44 int u=dfs(t.to,min(t.cap,f)); 45 t.cap-=u;E[t.to][t.rev].cap+=u; 46 f-=u;r+=u; 47 } 48 } 49 return r; 50 } 51 int dinic(){ 52 int flow_sum=0; 53 while(bfs()) flow_sum+=dfs(st,maxn); 54 return flow_sum; 55 } 56 57 int main(){ 58 int a,b,maxx,minn; 59 scanf("%d%d",&n,&m); 60 for(int i=0;i<m;i++){ 61 scanf("%d%d%d%d",&a,&b,&minn,&maxx); 62 flow[i+1]=minn; 63 du[a]-=minn;du[b]+=minn; 64 Add_Edge(a,b,maxx-minn,i+1); 65 } 66 st=0;sd=n+1; 67 for(int i=1;i<=n;i++){ 68 if(du[i]>0) Add_Edge(st,i,du[i],0); 69 if(du[i]<0) Add_Edge(i,sd,-du[i],0); 70 } 71 dinic(); 72 bool flag=true; 73 for(int i=st;i<=sd;i++){ 74 for(int j=0;j<E[i].size();j++){ 75 int k=E[i][j].num; 76 if(k%2==1){ 77 k=k/2; 78 if(1<=k && k<=m) flow[k]+=E[i][j].cap; 79 } 80 else{ 81 if(k==0 && E[i][j].cap>0) flag=false; 82 } 83 84 } 85 } 86 if(flag){ 87 printf("YES\n"); 88 for(int i=1;i<=m;i++) printf("%d\n",flow[i]); 89 } 90 else{ 91 printf("NO\n"); 92 } 93 return 0; 94 }

?

posted on 2017-03-16 22:14 學(xué)無(wú)止境-1980 閱讀(...) 評(píng)論(...) 編輯 收藏

轉(zhuǎn)載于:https://www.cnblogs.com/rdzrdz-acm/p/6561935.html

總結(jié)

以上是生活随笔為你收集整理的有上下界的网络流1-无源汇带上下界网络流SGU194的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。