一、定義與定理
      最小費用最大流：設(shè)G是以s為源t為匯的網(wǎng)絡(luò)，c是G的容量，b是G的單位流量費用，且有b[i][j] = -b[i][j]，f是G的流，則b(f)=∑(fij*bij)，(i, j)∈E(G) 且fij>0。最小費用最大流問題，就是求網(wǎng)絡(luò)G的最大流f且使費用b(f)最小。這樣的流稱為最小費用最大流。
二、算法思想
      用Ford-Fulkerson算法的思想，不斷地在殘留網(wǎng)絡(luò)中尋找增廣路，只不過這個增廣路是當(dāng)前網(wǎng)絡(luò)中s到t的以單位流量費用為權(quán)的最短路，對這條增廣路進行操作。由于費用有負值，建議用SPFA算法。
三、算法介紹
      描述：

      實現(xiàn)：

 1mcmf()
 2{
 3    while(true)
 4    {
 5        for(int i=1; i<=n+m+1; i++)
 6            d[i] = MAX;
 7        d[s] = 0;
 8        spfa(); //p中存有該點的前繼點
 9        if(p[t] == -1) //表示已無增廣路
10            break;
11        int minf = INT_MAX;
12        int it = t;
13        while(p[it] != -1)
14        {
15            minf = min(minf, c[p[it]][it] - f[p[it]][it]);
16            it = p[it];
17        }
18        it = t;
19        while(p[it] != -1)
20        {
21            f[p[it]][it] += minf;
22            f[it][p[it]] = -f[p[it]][it];
23            it = p[it];
24        }
25    }
26}

三、算法示例
      POJ 2516 解題報告