本文共 4036 字，大约阅读时间需要 13 分钟。
看了很多人讲解的最小费用最大流，但是讲的都太不清楚了，感觉还是这个清楚
看了一个星期，把其中的各种变量都拆了出来，终于把最小费用最大流的各种细节明白了，
我认为理解这个算法的还是理解剩余网络
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 using namespace std; 14 15 int maxData = 0x3fffffff; 16 17 int augment(int v, vector pre, int cap, vector > &capacity, 18 vector > &residual, vector > 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 &pre, vector > &capacity, 44 vector > &residual, vector > cost_graph) { 45 int n = capacity.size(); 46 queue myqueue; 47 int i; 48 vector d(n, maxData); //将除源点以外的其余点的距离设置为无穷大 49 d[s] = 0; //源点的距离为0 50 51 for (i = 0; i < n; ++i) { //初始化前驱 52 pre[i] = -1; 53 } 54 vector 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 > &capacity, 92 vector > cost_graph) { 93 94 int increasement = 0; //增广路径的值 95 int n = capacity.size(); 96 vector > residual(n, vector (n, 0)); //剩余网络 97 vector 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 dominoes) {110 int n = dominoes.size();111 int total = 0;112 int useless=0;113 vector > path(n + 2, vector (n + 2, 0));114 vector > cost_graph(n + 2, vector (n + 2, 1));115 vector > connected(n, vector (n, false));116 vector 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
转载于:https://www.cnblogs.com/kakamilan/archive/2012/08/17/2644315.html