原題鏈接：http://www.lydsy.com/JudgeOnline/problem.php?id=3597

?

Description

四川的方伯伯為了致富，決定引進海南的椰子樹。方伯伯的椰子園十分現代化，椰子園中有一套獨特的交通系統。

現在用點來表示交通節點，邊來表示道路。這樣，方伯伯的椰子園就可以看作一個有 n + 2 個交通節點，m條邊的有向無環圖。n +1 號點為入口，n +2 號點為出口。每條道路都有 6 個參數，ui，vi，ai，bi，ci，di，分別表示，該道路從 ui 號點通向 vi 號點，將它的容量壓縮一次要 ai 的花費，容量擴大一次要 bi 的花費，該條道路當前的運輸容量上限為 ci，并且每單位運輸量通過該道路要 di 的費用。

在這個交通網絡中，只有一條道路與起點相連。因為弄壞了這條道路就會導致整個交通網絡癱瘓，聰明的方伯伯決定絕不對這條道路進行調整，也就是說，現在除了這條道路之外，對其余道路都可以進行調整。

有兩種調整方式：

選擇一條道路，將其進行一次壓縮，這條道路的容量會下降 1 單位。

選擇一條道路，將其進行一次擴容，這條道路的容量會上升 1 單位。

一條道路可以被多次調整。

由于很久以前，方伯伯就請過一個工程師，對這個交通網絡進行過一次大的優化調整。所以現在所有的道路都被完全的利用起來了，即每條道路的負荷都是滿的（每條道路的流量等于其容量）。

但方伯伯一想到自己的海南椰子會大豐收，就十分擔心巨大的運輸量下，會導致過多的花費。因此，方伯伯決定至少進行一次調整，調整之后，必須要保持每條道路滿負荷，且總交通量不會減少。

設調整后的總費用是 Y，調整之前的總費用是 X?，F在方伯伯想知道，最優調整比率是多少，即假設他進行了 k 次調整，(X - Y)/k最大能是多少？

注：總費用 = 交通網絡的運輸花費 + 調整的花費

Input

第一行包含二個整數N，M接下來M行代表M條邊，表示這個交通網絡每行六個整數，表示Ui,Vi,Ai,Bi,Ci,Di接下來一行包含一條邊，表示連接起點的邊

Output

一個浮點數，保留二位小數。表示答案，數據保證答案大于0

Sample Input

5 10
1 5 13 13 0 412
2 5 30 18 396 148
1 5 33 31 0 39
4 5 22 4 0 786
4 5 13 32 0 561
4 5 3 48 0 460
2 5 32 47 604 258
5 7 44 37 75 164
5 7 34 50 925 441
6 2 26 38 1000 22

Sample Output

103.00

HINT

1<=N<=500,0<=M<=3000,1<=Ui,Vi<=N+2,0<=Ai,Bi<=500,0<=Ci<=10000,0<=Di<=1000

?

?

?

題意概述：
　　給出一個N+2個點M條邊的DAG圖，這是一張網絡，每條邊有縮容1的代價a，擴容1的代價b，流量上限c，流量費用d。一開始網絡中每條邊都是滿流的?，F在可以對網絡進行一些調整（不包括和起點相連的唯一的那條邊），調整之后使得網絡中的所有邊依舊滿流（即同時流量大小不變）。
　　假設進行了K次調整，調整之前的總流量費用為X，調整中花費的費用以及調整之后的流量費用為Y，問(X-Y)/K的最大值（答案保證大于0）。

?

分析：
　　哎呀呀先分析性質。。。。。
　　題目給的(X-Y)/K長得很難看。。發現每一次操作只會讓某一條邊新的流量的代價增加/減少單位代價，所以說這個式子實際上求的是合法調整方案每次操作的單位代價。
　　最終的總流量不能變，那么事實上我們不能增流或者減流，只能調整流量。在殘量網絡之中一個合法的改流對應了一個環（可以遞歸證明，因為這是個DAG圖所以不存在正權環無效改流的情況）。對于一次增流操作，付出的代價為d+b；對于一次減流操作，得到的收益為d-a。當存在一個環中所有邊的調整代價為負數，即得到一個負權環的時候，這種調整給我們帶來了收益。
　　題目的問法顯然是個最優比率問題，那么考慮二分答案。假設當前二分到的值為m，假設存在一種方案，所有被操作的邊的收益和為sum，操作邊的數量為cnt，那么有sum/cnt>=m，雖然這其中可能有很多個環，但是根據糖水原理一定至少包含一個環單獨滿足這個性質。于是對于這單獨的一個環，式子變成：cnt*m-sum<=0，cnt表示的是環上邊的數量。分到每條邊的頭上就是sum{m-w}<=0，其中w代表的是這條邊的收益（原圖的邊正向連邊，收益-(d+b)，反向連邊，收益為(d-a)）。對于原圖中沒有流量的邊，不連反向邊。二分答案的時候看有沒有負權環，有的話說明答案成立，可以往大猜，否則不成立，只能往小猜。
　　二分下界為0，上界為所有邊d的和。
　　最壞時間復雜度：O((34)*N*M)

?

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<queue> 7 #include<set> 8 #include<map> 9 #include<vector> 10 #include<cctype> 11 #define inf (1e9+5) 12 using namespace std; 13 const int maxn=505; 14 const int maxm=3005; 15 const double eps=1e-4; 16 17 int N,M; 18 struct net_edge{ int u,v,a,b,c,d; }NE[maxm]; 19 struct edge{ int to,next; double w; }E[maxm<<1]; 20 int first[maxn],np,inq[maxn],inc[maxn],sum; double dist[maxn]; 21 22 void data_in() 23 { 24 scanf("%d%d",&N,&M); 25 for(int i=1;i<=M;i++){ 26 scanf("%d%d%d%d%d%d",&NE[i].u,&NE[i].v,&NE[i].a,&NE[i].b,&NE[i].c,&NE[i].d); 27 sum+=NE[i].d; 28 } 29 } 30 void add_edge(int u,int v,double w) 31 { 32 E[++np]=(edge){v,first[u],w}; 33 first[u]=np; 34 } 35 bool SPFA() 36 { 37 for(int i=1;i<=N+2;i++) dist[i]=inf,inc[i]=inq[i]=0; 38 queue<int>q; 39 q.push(N+1); 40 dist[N+1]=0,inq[N+1]=1,inc[N+1]=1; 41 while(!q.empty()){ 42 int i=q.front(); q.pop(); 43 inq[i]=0; 44 for(int p=first[i];p;p=E[p].next){ 45 int j=E[p].to; 46 if(dist[i]+E[p].w<dist[j]){ 47 dist[j]=dist[i]+E[p].w, 48 if(!inq[j]){ 49 if(++inc[j]==N+2) return 1; 50 inq[j]=1,q.push(j); 51 } 52 } 53 } 54 } 55 return 0; 56 } 57 bool check(double m) 58 { 59 memset(first,0,sizeof(first)); 60 np=0; 61 for(int i=1;i<=M;i++){ 62 add_edge(NE[i].u,NE[i].v,m+(NE[i].d+NE[i].b)); 63 if(NE[i].c) add_edge(NE[i].v,NE[i].u,m-(NE[i].d-NE[i].a)); 64 } 65 return SPFA(); 66 } 67 void work() 68 { 69 double L=0,R=sum,mid,ans=0; 70 while(R-L>=eps){ 71 mid=(L+R)/2; 72 if(check(mid)) ans=mid,L=mid; 73 else R=mid; 74 } 75 printf("%.2f\n",ans); 76 } 77 int main() 78 { 79 data_in(); 80 work(); 81 return 0; 82 } View Code

?

轉載于:https://www.cnblogs.com/KKKorange/p/8601144.html

總結

以上是生活随笔為你收集整理的BZOJ 3597 SCOI2014 方伯伯送椰子 网络流分析+SPFA的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。