?

　　今天學習了最小費用最大流，是網絡流算法之一。可以對于一個每條邊有一個容量和一個費用（即每單位流的消耗）的圖指定一個源點和匯點，求在從源點到匯點的流量最大的前提下的最小費用。

　　這里講一種最基礎也是最好掌握的實現算法，就是spfa求費用流。

　　其實也很簡單，在最大流的基礎上，我們將dfs增廣替換成對于費用為權值的邊跑spfa得到的最短路，相當于一個貪心的思想。證明有一定難度，稍微口糊一下，就像ford-fulkerson一樣，這個算法每次都能找到一條單位流費用和最小的路徑，又由于路徑中每條邊的流量相等，每次增廣就能使得單位流量的平均費用更小，而最大流流量是不變的，這樣就能使得費用最小。

　　網絡流算法主要考建圖，所以模板只要會默下來就夠了，還有就是：

　　一定要會寫spfa！！！

?

　　對于spfa，這里有兩個小優化。

　　一個是slf優化，就是對于spfa的進隊操作，進之前判一下若小于隊頭就直接插在隊頭，這個還是蠻有用的，可以提升點速度；

　　另一個是記路徑的時候可以不用記前趨點，只要記邊，反向邊指向的就是前趨，就不用多開一個數組的空間。(這個是zxyer學長當時說的)

?

　　下面貼上代碼：

　　這是網絡流24題中的餐巾計劃問題。

　　題目大意是：一個飯館每天需要使用ri條干凈的餐巾，用完就臟了，干凈餐巾可以由3種方式得到：

　　　　1.直接購買，p元一條；

　　　　2.快洗，需要t1天，花費w1元；

　　　　3.慢洗，需要t2天，花費w2元；

　　所以我們建6種邊，把每天拆成兩個點，分別為干凈的（1~n）和臟的（n+1~n*2），這里要注意的是，干凈的不直接向臟的連邊，而是連向T，相當于必須送滿ri條給顧客使用，再從S送到臟的一邊。

1 #include<cstdio> 2 using namespace std; 3 const int inf=2147483647; 4 int n,m,p,t1,w1,t2,w2,tot=1,mx,q[2010],d[2010],pree[2010],h[2010]; 5 struct edge{int to,nxt,cst,cap;}e[10010]; 6 bool vis[2010]; 7 int mn(int x,int y){return x>y?y:x;} 8 void add(int fr,int to,int cst,int cap) 9 { 10 e[++tot]={to,h[fr],cst,cap};h[fr]=tot; 11 e[++tot]={fr,h[to],-cst,0};h[to]=tot;//建一條容量為0費用為-cap的反向邊且滿足正反邊異或值為1方便將邊取反 12 } 13 void init() 14 { 15 scanf("%d%d%d%d%d%d",&n,&p,&t1,&w1,&t2,&w2); 16 for(int i=1;i<=n;i++) 17 { 18 int r;scanf("%d",&r);mx+=r; 19 add(0,n+i,p,inf);//直接購買花費p元 20 add(0,i,0,r);//當天用完的舊餐巾 21 add(i+n,n*2+1,0,r);//當天需要使用的新餐巾 22 if(i+t1<=n)add(i,i+n+t1,w1,inf);//快洗花費t1時間，每條w1元 23 if(i+t2<=n)add(i,i+n+t2,w2,inf);//快洗花費t2時間，每條w2元 24 if(i<n)add(i,i+1,0,inf);//不需要做任何事的餐巾積到明天（也可以先洗完然后放在那邊等就是n+i連向n+i+1） 25 } 26 n=n*2+1; 27 } 28 bool spfa() 29 { 30 for(int i=1;i<=n;i++)d[i]=inf; 31 int l=0,r=1;q[1]=0;vis[0]=1; 32 while(l!=r) 33 { 34 int x=q[l=l==n?0:l+1]; 35 for(int i=h[x];i;i=e[i].nxt) 36 if(e[i].cap&&e[i].cst+d[x]<d[e[i].to]) 37 { 38 int v=e[i].to; 39 pree[v]=i; 40 d[v]=d[x]+e[i].cst; 41 if(!vis[v]) 42 { 43 if(d[v]>d[l+1])q[r=r==n?0:r+1]=v; 44 else q[l]=v,l=l==0?n:l-1;//這邊加的是slf優化，用了循環隊列來寫 45 vis[v]=1; 46 } 47 } 48 vis[x]=0; 49 } 50 return d[n]==inf?0:1; 51 } 52 int costflow() 53 { 54 int cost=0,mm=0; 55 while(spfa()) 56 { 57 int mi=inf; 58 for(int i=n;i;i=e[pree[i]^1].to)//記路徑時記下前趨路徑 59 mi=mn(mi,e[pree[i]].cap); 60 for(int i=n;i;i=e[pree[i]^1].to) 61 { 62 int ee=pree[i]; 63 e[ee].cap-=mi; 64 e[ee^1].cap+=mi; 65 } 66 cost+=d[n]*mi; 67 mm+=mi; 68 } 69 return mm==mx?cost:0;//是否滿流的判斷(這道題不會出現不滿流的情況，所以不加也可) 70 } 71 int main() 72 { 73 init(); 74 printf("%d",costflow()); 75 return 0; 76 }

?

??

轉載于:https://www.cnblogs.com/qrcer/p/6582783.html

總結

以上是生活随笔為你收集整理的初识费用流 模板(spfa+slf优化) 餐巾计划问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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