看了下SPFA題解，一個一個太麻煩了，另一個寫的很不清楚，而且注釋都變成了"????"不知道怎么過的，于是自己來一發(fā)SPFA算法。

Part 1.題意

M 個倉庫，賣給 N?個商店，兩個問，第一問求運價最小值，第二問最大值。

顯然是一個最小費用最大流(MCMF)。

Part 2.思路

1.連讓每個倉庫連接一個超級源點?SS?，費用(dis)為0，流量為倉庫的流量，表示每個倉庫最多可以運出多少貨物。

2.讓每一個倉庫連接每一家商店，邊權為?cost[i][j]?，其中，i為倉庫編號，j為商店編號編號，流量為?need[j]?，其實流量可以取得范圍是??[need[j]...INF]?，另外如果出現(xiàn)?need[j]?<這個倉庫貨物量的情況也可以不怕(這時候取值的下限變成?min(hw[i],need[j])?) hw指的是這家倉庫的貨物，還有注意編號的范圍（我默認超級源點是?00?，倉庫是?1……n?,商店是?n+1……n+m?，超級匯點是?10000）

3.讓每一家商店連接超級匯點?TT

圖像幫助理解：?

Part 3.代碼

現(xiàn)在代碼就好辦了 注釋給的很清楚

1 #include<iostream> 2 #include<cmath> 3 #include<cstdio> 4 #include<cstring> 5 #include<queue> 6 #include<stack> 7 #include<vector> 8 #include<map> 9 #include<set> 10 #include<algorithm> 11 12 #define I_copy_this_answer return 0; 13 14 using namespace std; 15 16 int n,m,head[1100],size=1; 17 int mmx=1000,mincost,maxwater; 18 int flow[1100]; 19 int need[1100],cost[310][310]; 20 int pre[1100],las[1100],dis[1100],vis[1100],hw[1100]; 21 22 struct edge{ 23 int next,to,dis,flow; 24 }e[100860]; 25 26 void addedge(int next,int to,int dis,int flow) 27 { 28 e[++size].to=to; 29 e[size].dis=dis; 30 e[size].flow=flow; 31 e[size].next=head[next]; 32 head[next]=size; 33 } 34 35 int spfa(int s) 36 { 37 memset(flow,0x3f,sizeof(flow)); 38 memset(dis,0x3f,sizeof(dis)); 39 memset(vis,0,sizeof(vis)); 40 queue <int> q; 41 q.push(s); 42 dis[s]=0; 43 vis[s]=1; 44 pre[mmx]=-1; //（其實只要不是與p直接連的點(n+1......n+m)就可以了 45 while(!q.empty()) 46 { 47 int t=q.front(); 48 q.pop(); 49 vis[t]=0; 50 int i,j,k,l; 51 for(i=head[t];i;i=e[i].next) 52 { 53 j=e[i].to; 54 k=e[i].dis; 55 l=e[i].flow; 56 if(dis[t]+k<dis[j]&&l>0) //沒有流量的話這條路就增廣不了，最短距離是建立在增廣路存在的基礎上的 57 { 58 dis[j]=dis[t]+k; 59 las[j]=i; //las指的是這個點(j)與上個點(t)相連的邊的編號 60 pre[j]=t; //pre指的是這條路徑上這個點(j)的上一個點 61 flow[j]=min(flow[t],l); //把當前邊流量與上個點的流量對比，解決出現(xiàn)倉庫貨物比需要的少的情況 62 if(!vis[j]) 63 { 64 q.push(j); 65 vis[j]=1; 66 } 67 } 68 } 69 } 70 return pre[mmx]!=-1; //如果不是這個值就說明這個點被刷新，增廣成功 71 } 72 73 void mcmf() 74 { 75 while(spfa(0)) 76 { 77 mincost+=dis[mmx]*flow[mmx]; //從源點出發(fā)到匯點的單位費用再乘以單位，由于每次只增廣一條路，而且倉庫和商店是直接連接的，可以這樣寫 78 int t=mmx; 79 while(t!=0) 80 { 81 e[las[t]].flow-=flow[mmx]; //回溯，修改每條邊的流量，因為該算法中途找到的增廣路不是最后的增廣路，所以這個要等到最后來改變 82 e[las[t]^1].flow+=flow[mmx]; 83 t=pre[t]; 84 } 85 } 86 } 87 88 void build_edge(int t) 89 { 90 int i,j; 91 for(i=1;i<=m;i++) 92 { 93 addedge(0,i,0,hw[i]); 94 addedge(i,0,0,0); 95 } 96 for(i=1;i<=m;i++) 97 for(j=1;j<=n;j++) 98 { 99 addedge(i,j+m,cost[i][j]*t,need[j]); 100 addedge(j+m,i,-cost[i][j]*t,0); 101 } 102 for(i=1;i<=n;i++) 103 { 104 addedge(i+m,mmx,0,need[i]); 105 addedge(mmx,i+m,0,0); 106 } 107 } 108 109 int main() 110 { 111 int i,j; 112 scanf("%d %d",&m,&n); 113 for(i=1;i<=m;i++) 114 { 115 int t1; 116 scanf("%d",&hw[i]); 117 } 118 for(i=1;i<=n;i++) 119 scanf("%d",&need[i]); 120 for(i=1;i<=m;i++) 121 for(j=1;j<=n;j++) 122 scanf("%d",&cost[i][j]); //讀入，與上面的cost,need,hw如果不明白可以對照輸入格式看代表什么意思 123 build_edge(1); //建立邊權為正的邊，跑最小費用最大流 124 mcmf();//最小費用最大流(Min Cost Max Flow ）的縮寫 125 printf("%d",mincost); 126 maxwater=0; 127 mincost=0; 128 size=1; 129 memset(head,0,sizeof(head)); 130 build_edge(-1); 131 mcmf(); 132 printf("\n%d",-mincost); 133 I_copy_this_answer 134 }

?

轉載于:https://www.cnblogs.com/zsx6/p/11174387.html

總結

以上是生活随笔為你收集整理的洛谷P4015 运输问题 网络流24题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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