看了很多人讲解的最小费用最大流，但是讲的都太不清楚了，感觉还是这个清楚
http://www.strongczq.com/2012/03/srm537-div1-3-princexdominoes.html
看了一个星期，把其中的各种变量都拆了出来，终于把最小费用最大流的各种细节明白了，
我认为理解这个算法的还是理解剩余网络
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <cstdlib> 5 #include <cmath> 6 #include <map> 7 #include <algorithm> 8 #include <list> 9 #include <ctime> 10 #include <set> 11 #include <string.h> 12 #include <queue> 13 using namespace std; 14 15 int maxData = 0x3fffffff; 16 17 int augment(int v, vector<int> pre, int cap, vector<vector<int> > &capacity, 18 vector<vector<int> > &residual, vector<vector<int> > cost_graph, 19 int& cost) { 20 int u = pre[v]; 21 int r = residual[u][v] > 0 ? 1 : 0; 22 int minCap; 23 if (r == 0) { 24 minCap = min(cap, capacity[u][v]); 25 } else { 26 minCap = min(cap, residual[u][v]); 27 } 28 29 if (u != 0) { 30 minCap = augment(u, pre, minCap, capacity, residual, cost_graph, cost); 31 } 32 if (r == 0) { 33 capacity[u][v] -= minCap; 34 residual[v][u] += minCap; 35 } else { 36 capacity[v][u] += minCap; 37 residual[u][v] -= minCap; 38 } 39 cost += (r == 0 ? cost_graph[u][v] : -cost_graph[v][u]) * minCap; 40 return minCap; 41 } 42 43 int SPFA(int s, int des, vector<int> &pre, vector<vector<int> > &capacity, 44 vector<vector<int> > &residual, vector<vector<int> > cost_graph) { 45 int n = capacity.size(); 46 queue<int> myqueue; 47 int i; 48 vector<int> d(n, maxData); //将除源点以外的其余点的距离设置为无穷大 49 d[s] = 0; //源点的距离为0 50 51 for (i = 0; i < n; ++i) { //初始化前驱 52 pre[i] = -1; 53 } 54 vector<bool> final(n, false); //记录顶点是否在队列中，SPFA算法可以入队列多次 55 56 final[s] = true; 57 myqueue.push(s); 58 int topint; 59 while (!myqueue.empty()) { 60 topint = myqueue.front(); 61 myqueue.pop(); 62 final[topint] = false; 63 for (i = 0; i < n; ++i) { 64 if (d[i] > d[topint] + cost_graph[topint][i] 65 && capacity[topint][i] > 0) { 66 d[i] = d[topint] + cost_graph[topint][i]; 67 pre[i] = topint; 68 if (!final[i]) { //判断是否在当前的队列中 69 final[i] = true; 70 myqueue.push(i); 71 } 72 } 73 74 if (d[i] > d[topint] - cost_graph[i][topint] 75 && residual[topint][i] > 0) { 76 d[i] = d[topint] - cost_graph[i][topint]; 77 pre[i] = topint; 78 if (!final[i]) { //判断是否在当前的队列中 79 final[i] = true; 80 myqueue.push(i); 81 } 82 } 83 } 84 } 85 86 if (pre[des] == -1) 87 return -1; 88 return 1; 89 } 90 91 int maxFlow(int src, int des, vector<vector<int> > &capacity, 92 vector<vector<int> > cost_graph) { 93 94 int increasement = 0; //增广路径的值 95 int n = capacity.size(); 96 vector<vector<int> > residual(n, vector<int>(n, 0)); //剩余网络 97 vector<int> pre(n, -1); //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列中 98 int cost = 0; 99 while ((increasement = SPFA(src, des, pre, capacity, residual, cost_graph)) 100 != -1) { 101 int cap = augment(des, pre, maxData, capacity, residual, cost_graph,cost); 102 } 103 104 return cost; 105 } 106 107 class PrinceXDominoes { 108 public: 109 int play(vector<string> dominoes) { 110 int n = dominoes.size(); 111 int total = 0; 112 int useless=0; 113 vector<vector<int> > path(n + 2, vector<int>(n + 2, 0)); 114 vector<vector<int> > cost_graph(n + 2, vector<int>(n + 2, 1)); 115 vector<vector<bool> > connected(n, vector<bool>(n, false)); 116 vector<int> red_minus_black(n, 0); 117 int i, j; 118 for (int i = 0; i < n; ++i) { 119 connected[i][i] = true; 120 } 121 for (int i = 0; i < n + 2; ++i) { 122 cost_graph[i][i] = 0; 123 } 124 for (i = 0; i < n; i++) { 125 for (j = 0; j < n; j++) { 126 if (dominoes[i][j] != '.') { 127 int tmp = dominoes[i][j] - 'A' + 1; 128 path[i + 1][j + 1] = tmp - 1; 129 total = total + tmp; 130 red_minus_black[i] += tmp; 131 red_minus_black[j] -= tmp; 132 connected[i][j] = true; 133 } 134 } 135 } 136 137 for (int k = 0; k < n; ++k) 138 for (int i = 0; i < n; ++i) 139 for (int j = 0; j < n; ++j) { 140 connected[i][j] = connected[i][j] 141 || (connected[i][k] && connected[k][j]); 142 } 143 144 for (int i = 0; i < n; ++i) 145 for (int j = 0; j < n; ++j) 146 if (!connected[i][j]) { 147 return -1; 148 } 149 150 for (int i = 0; i < n; ++i) { //初始化src和des点 151 if (red_minus_black[i] > 0) { 152 path[0][i + 1] = red_minus_black[i]; 153 useless +=red_minus_black[i]; 154 } else { 155 path[i + 1][n + 1] = -red_minus_black[i]; 156 useless -=red_minus_black[i]; 157 } 158 } 159 int res = maxFlow(0, n + 1, path, cost_graph); 160 for(int i=0;i<n+2;i++){ 161 if(path[0][i]!=0){ 162 return -1; 163 } 164 } 165 166 return total - res+2*useless; 167 } 168 169 };