最小费用最大流

网络流的最后一步。之前已经写了最大流的Dinic，SAP，EK这三种算法。
  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <algorithm>
  4 #include <queue>
  5 #include <math.h>
  6 #include <stdio.h>
  7 #include <string.h>
  8 #include <algorithm>
  9 #include <functional>
 10 
 11 #define MAXN 5050
 12 #define INF 0x3f3f3f3f
 13 #define P pair<int,int>
 14 
 15 using namespace std;
 16 
 17 struct edge
 18 {
 19     int to, cap, cost, rev;
 20 };
 21 
 22 int n, m, s, t;
 23 int u, v, c, w;
 24 int maxFlow, minCost;
 25 
 26 vector<edge> G[MAXN];
 27 int h[MAXN];
 28 int dist[MAXN], prevv[MAXN], preve[MAXN];
 29 
 30 void addedge(int from, int to, int cap, int cost)
 31 {
 32     edge temp1 = { to, cap, cost, (int)G[to].size() };
 33     edge temp2 = { from, 0, -cost, (int)G[from].size() - 1 };
 34     G[from].push_back(temp1);
 35     G[to].push_back(temp2);
 36 }
 37 
 38 //Dijkstra算法实现
 39 void MCMF(int s, int t, int f)
 40 {
 41     fill(h + 1, h + 1 + n, 0);
 42     while (f > 0)
 43     {
 44         priority_queue<P, vector<P>, greater<P> > D;
 45         memset(dist, INF, sizeof dist);
 46         dist[s] = 0; D.push(P(0, s));
 47         while (!D.empty())
 48         {
 49             P now = D.top(); D.pop();
 50             if (dist[now.second] < now.first) continue;
 51             int v = now.second;
 52             for (int i = 0; i<(int)G[v].size(); ++i)
 53             {
 54                 edge &e = G[v][i];
 55                 if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to])
 56                 {
 57                     dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
 58                     prevv[e.to] = v;
 59                     preve[e.to] = i;
 60                     D.push(P(dist[e.to], e.to));
 61                 }
 62             }
 63         }
 64         if (dist[t] == INF) break;
 65         for (int i = 1; i <= n; ++i) h[i] += dist[i];
 66         int d = f;
 67         for (int v = t; v != s; v = prevv[v])
 68             d = min(d, G[prevv[v]][preve[v]].cap);
 69         f -= d; maxFlow += d;
 70         minCost += d * h[t];
 71         for (int v = t; v != s; v = prevv[v])
 72         {
 73             edge &e = G[prevv[v]][preve[v]];
 74             e.cap -= d;
 75             G[v][e.rev].cap += d;
 76         }
 77     }
 78 }
 79 
 80 int _tmain(int argc, _TCHAR* argv[])
 81 {
 82 
 83     cout << "节点数为："; cin >> n;
 84     cout << "边数为："; cin >> m;
 85     cout << "源点编号为："; cin >> s;
 86     cout << "汇点编号为："; cin >> t;
 87 
 88     cout << "输入 " << m << " 条边的信息：" << endl;
 89     while (m--)
 90     {
 91         cout << "起点："; cin >> u;
 92         cout << "终点："; cin >> v;
 93         cout << "容量："; cin >> c;
 94         cout << "费用："; cin >> w;
 95         cout << "-----------------" << endl;
 96         addedge(u, v, c, w);
 97     }
 98 
 99     MCMF(s, t, INF);
100 
101     cout << "最大流为：" << maxFlow << endl;
102     cout << "最小费用为" << minCost << endl;
103     cout << endl;
104 
105     system("pause");
106     return 0;
107 }