洛谷P4016 負(fù)載平衡問(wèn)題

題目大意:

　　G 公司有 n 個(gè)沿鐵路運(yùn)輸線環(huán)形排列的倉(cāng)庫(kù)，每個(gè)倉(cāng)庫(kù)存儲(chǔ)的貨物數(shù)量不等。如何用最少搬運(yùn)量可以使 n 個(gè)倉(cāng)庫(kù)的庫(kù)存數(shù)量相同。搬運(yùn)貨物時(shí)，只

能在相鄰的倉(cāng)庫(kù)之間搬運(yùn)。

思路：

　　最小費(fèi)用最大流。

　　假設(shè)物品的總庫(kù)存之和為sum，那么為了使庫(kù)存之和相等，搬運(yùn)結(jié)束后每一個(gè)倉(cāng)庫(kù)的目標(biāo)庫(kù)存量ave應(yīng)該都等于sum/n。

　　這時(shí)候很顯然，我們發(fā)現(xiàn)初始庫(kù)存量>ave的倉(cāng)庫(kù)會(huì)向其他倉(cāng)庫(kù)搬運(yùn)貨物，而初始庫(kù)存量<ave的倉(cāng)庫(kù)會(huì)接收貨物。

　　所以我們將所有倉(cāng)庫(kù)的初始貨物數(shù)nums[i]減去ave，如果nums[i]-ave>0，那么由超級(jí)源點(diǎn)向他發(fā)出一條流量為nums[i]-ave，費(fèi)用為0的邊。

　　如果nums[i]-ave<0，那么由他向超級(jí)匯點(diǎn)發(fā)出一條流量為ave-nums[i]，費(fèi)用為0的邊。

　　最后再在所有相鄰的倉(cāng)庫(kù)之間互相建立流量為無(wú)窮大，費(fèi)用為1的雙向邊。

　　然后就沒(méi)有然后了。。。

我的錯(cuò)誤o(╥﹏╥)o

　　1、一開(kāi)始直接跑了最大流，結(jié)果WA了9個(gè)點(diǎn)，后來(lái)發(fā)現(xiàn)最大流無(wú)法計(jì)算轉(zhuǎn)移量之和，其實(shí)這是一個(gè)很蠢的錯(cuò)誤、、、

　　2、加雙向邊的時(shí)候有一個(gè)細(xì)節(jié)，因?yàn)槲矣玫氖青徑颖?#xff0c;一開(kāi)始加雙向邊的時(shí)候沒(méi)有加入費(fèi)用為負(fù)的輔助邊，結(jié)果還是WA了9個(gè)點(diǎn)。。。

代碼：

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 using namespace std; 7 #define MAXN 110 8 struct Node{ 9 int u,v,w,c; 10 Node(){} 11 Node(int u,int v,int w,int c):u(u),v(v),w(w),c(c){} 12 }p[MAXN<<3]; 13 struct Record{ 14 int u,dis; 15 Record(){} 16 Record(int u,int dis):u(u),dis(dis){} 17 bool operator < (const Record & a) const{ 18 return dis>a.dis; 19 } 20 }; 21 int head[MAXN],Next[MAXN<<3],nums[MAXN],dis[MAXN],pre[MAXN],preNode[MAXN]; 22 bool vis[MAXN]; 23 int i,j,k,m,n,tot,sum; 24 void addNode(int u,int v,int w,int c){ 25 p[++tot]=Node(u,v,w,c); 26 Next[tot]=head[u],head[u]=tot; 27 p[++tot]=Node(v,u,0,-c); 28 Next[tot]=head[v],head[v]=tot; 29 } 30 bool dijkstra(int src,int goal){ 31 priority_queue<Record> mque; 32 while(!mque.empty()) mque.pop(); 33 for(register int i=0;i<=n+1;i++) vis[i]=false,dis[i]=1000000000; 34 mque.push(Record(src,0)); 35 vis[src]=true; dis[src]=0; 36 pre[src]=-1; 37 while(!mque.empty()){ 38 Record tmp=mque.top(); mque.pop(); 39 if(dis[tmp.u]<tmp.dis) continue; 40 //if(vis[tmp.u]) continue; 41 for(register int i=head[tmp.u];i+1;i=Next[i]){ 42 if(p[i].w&&dis[tmp.u]+p[i].c<dis[p[i].v]){ 43 pre[p[i].v]=tmp.u; 44 preNode[p[i].v]=i; 45 dis[p[i].v]=dis[tmp.u]+p[i].c; 46 mque.push(Record(p[i].v,dis[p[i].v])); 47 } 48 } 49 } 50 if(dis[goal]!=1000000000) return true; 51 return false; 52 } 53 int dinic(int src,int goal){ 54 int ans=0; 55 while(dijkstra(src,goal)){ 56 int minf=1000000000; 57 for(register int i=goal;i!=src;i=pre[i]){ 58 minf=min(minf,p[preNode[i]].w); 59 } 60 for(register int i=goal;i!=src;i=pre[i]){ 61 p[preNode[i]].w-=minf; 62 p[preNode[i]^1].w+=minf; 63 } 64 ans+=dis[goal]*minf; 65 } 66 return ans; 67 } 68 int main(){ 69 scanf("%d",&n); 70 sum=0; 71 for(i=1;i<=n;i++) scanf("%d",nums+i),sum+=nums[i]; 72 sum/=n; 73 for(i=0;i<=n+1;i++) head[i]=-1; 74 tot=-1; 75 for(i=1;i<=n;i++) nums[i]-=sum; 76 for(i=1;i<=n;i++) if(nums[i]>0) addNode(0,i,nums[i],0); else { if(nums[i]<0) addNode(i,n+1,-nums[i],0); } 77 for(i=1;i<=n-1;i++) addNode(i,i+1,10000000,1),addNode(i+1,i,10000000,1); 78 addNode(n,1,10000000,1),addNode(1,n,10000000,1); 79 printf("%d\n",dinic(0,n+1)); 80 return 0; 81 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/linxif2008/p/9532392.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P4016 负载平衡问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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