HDU 4862 Jump (2014-多校1-1002，最小K路径覆盖，最小费用最大流)
题目：
http://acm.hdu.edu.cn/showproblem.php?pid=4862
题意：
给你一个n*m的矩阵，填充着0-9的数字，每次能从一个点出发，到它的右边或者下边的点，花费为|x1-x2|+|y1-y2|-1，如果跳跃的起点和终点的数字相同，则获得这个数字的收益，不能走已经走过的点
有K次重新选择起点的机会
如果可以走遍所有点，则输出最大的价值(收益-花费)
否则，输出-1
方法：
最小K路径覆盖，最小费用最大流
建图：
每个点拆为2点：X部和Y部，(a,b)表示流量a，费用b
源点与X部每个点连(1,0)的边
Y部每个点与汇点连(1,0)的边
X部的点如果可以到Y部的点，则连(1,花费-收益)的边
源点与一个新点连(k,0)的边，新点与Y部每个点连(1,0)的边
结果：
如果满流，则输出0-费用
否则，输出-1
代码：
1 // #pragma comment(linker, "/STACK:102400000,102400000") 2 #include <cstdio> 3 #include <iostream> 4 #include <cstring> 5 #include <string> 6 #include <cmath> 7 #include <set> 8 #include <list> 9 #include <map> 10 #include <iterator> 11 #include <cstdlib> 12 #include <vector> 13 #include <queue> 14 #include <stack> 15 #include <algorithm> 16 #include <functional> 17 using namespace std; 18 typedef long long LL; 19 #define ROUND(x) round(x) 20 #define FLOOR(x) floor(x) 21 #define CEIL(x) ceil(x) 22 // const int maxn = 210; 23 // const int maxm = 200010; 24 // const int inf = 0x3f3f3f3f; 25 const LL inf64 = 0x3f3f3f3f3f3f3f3fLL; 26 const double INF = 1e30; 27 const double eps = 1e-6; 28 const int P[4] = {0, 0, -1, 1}; 29 const int Q[4] = {1, -1, 0, 0}; 30 const int PP[8] = { -1, -1, -1, 0, 0, 1, 1, 1}; 31 const int QQ[8] = { -1, 0, 1, -1, 1, -1, 0, 1}; 32 33 /** 34 *最小(大)费用最大流：SPFA增广路($O(w*O(SPFA))$) 35 *最大费用：费用取反addEdge(,,,-cost); 36 *输入：图(链式前向星),n(顶点个数,包含源汇),s(源),t(汇) 37 *输出：minCostMaxflow(int s, int t, int &cost)返回流量, cost为费用 38 *打印路径方法：按反向边(i&1)的flow 找，或者按边的flow找 39 */ 40 const int maxn = 210; 41 const int maxm = 200010; 42 const int inf = 0x3f3f3f3f; 43 struct Edge 44 { 45 int u, v; 46 int cap, flow; 47 int cost; 48 int next; 49 } edge[maxm]; 50 int head[maxn], en; //需初始化 51 int n, m; 52 int st, ed; 53 bool vis[maxn]; 54 int pre[maxn], dis[maxn]; 55 void addse(int u, int v, int cap, int flow, int cost) 56 { 57 edge[en].u = u; 58 edge[en].v = v; 59 edge[en].cap = cap; 60 edge[en].flow = flow; 61 edge[en].cost = cost; 62 edge[en].next = head[u]; 63 head[u] = en++; 64 } 65 void adde(int u, int v, int cap, int cost) 66 { 67 addse(u, v, cap, 0, cost); 68 addse(v, u, 0, 0, -cost); //注意加反向0 边 69 } 70 bool spfa(int s, int t) 71 { 72 queue<int>q; 73 for (int i = 0; i < n; i++) 74 { 75 dis[i] = inf; 76 vis[i] = false; 77 pre[i] = -1; 78 } 79 dis[s] = 0; 80 vis[s] = true; 81 q.push(s); 82 while (!q.empty()) 83 { 84 int u = q.front(); 85 q.pop(); 86 vis[u] = false; 87 for (int i = head[u]; i != -1; i = edge[i].next) 88 { 89 int v = edge[i].v; 90 if (edge[i].cap > edge[i].flow && 91 dis[v] > dis[u] + edge[i].cost ) 92 { 93 dis[v] = dis[u] + edge[i].cost; 94 pre[v] = i; 95 if (!vis[v]) 96 { 97 vis[v] = true; 98 q.push(v); 99 } 100 } 101 } 102 } 103 if (pre[t] == -1)return false; 104 else return true; 105 } 106 int minCostMaxflow(int s, int t, int &cost)//返回流量, cost为费用 107 { 108 int flow = 0; 109 cost = 0; 110 while (spfa(s, t)) 111 { 112 int Min = inf; 113 for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].v]) 114 { 115 if (Min > edge[i].cap - edge[i].flow) 116 Min = edge[i].cap - edge[i].flow; 117 } 118 for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].v]) 119 { 120 edge[i].flow += Min; 121 edge[i ^ 1].flow -= Min; 122 cost += edge[i].cost * Min; 123 } 124 flow += Min; 125 } 126 return flow; 127 } 128 int N, M, K; 129 int kase; 130 int mtx[maxn][maxn]; 131 int disxy(int x1, int y1, int x2, int y2) 132 { 133 return abs(x1 - x2) + abs(y1 - y2) - 1; 134 } 135 void build() 136 { 137 n = 3 + N * M * 2; 138 st = 0, ed = 1; 139 for (int i = 0; i < N; i++) 140 { 141 for (int j = 0; j < M; j++) 142 { 143 adde(st, i * M + j + 3, 1, 0); 144 } 145 } 146 adde(st, 2, K, 0); 147 for (int i = 0; i < N; i++) 148 { 149 for (int j = 0; j < M; j++) 150 { 151 adde(2, i * M + j + N * M + 3, 1, 0); 152 adde(i * M + j + N * M + 3, ed, 1, 0); 153 } 154 } 155 for (int i = 0; i < N; i++) 156 { 157 for (int j = 0; j < M; j++) 158 { 159 for (int h = i + 1; h < N; h++) 160 { 161 if (mtx[i][j] == mtx[h][j]) 162 { 163 adde(i * M + j + 3, h * M + j + N * M + 3, 1, h - i - 1 - mtx[i][j]); 164 // cout << i << " " << j << " " << h << " " << j << endl; 165 } 166 else 167 { 168 adde(i * M + j + 3, h * M + j + N * M + 3, 1, h - i - 1); 169 } 170 } 171 for (int h = j + 1; h < M; h++) 172 { 173 if (mtx[i][j] == mtx[i][h]) 174 { 175 adde(i * M + j + 3, i * M + h + N * M + 3, 1, h - j - 1 - mtx[i][j]); 176 // cout << i << " " << j << " " << i << " " << h << endl; 177 } 178 else 179 { 180 adde(i * M + j + 3, i * M + h + N * M + 3, 1, h - j - 1); 181 } 182 } 183 } 184 } 185 } 186 void init() 187 { 188 memset(head, -1, sizeof(head)); 189 en = 0; 190 kase++; 191 } 192 void input() 193 { 194 scanf("%d%d%d", &N, &M, &K); 195 for (int i = 0; i < N; i++) 196 { 197 char str[maxn]; 198 scanf("%s", str); 199 for (int j = 0; j < M; j++) 200 { 201 mtx[i][j] = str[j] - '0'; 202 } 203 } 204 } 205 void debug() 206 { 207 // 208 } 209 void solve() 210 { 211 build(); 212 int cost; 213 int flow = minCostMaxflow(st, ed, cost); 214 // cout << "flow,cost: " << flow << " " << cost << endl; 215 if (flow == N * M) 216 { 217 printf("Case %d : %d ", kase, -cost); 218 } 219 else 220 { 221 printf("Case %d : %d ", kase, -1); 222 } 223 } 224 void output() 225 { 226 // 227 } 228 int main() 229 { 230 // int size = 256 << 20; // 256MB 231 // char *p = (char *)malloc(size) + size; 232 // __asm__("movl %0, %%esp " :: "r"(p)); 233 234 // std::ios_base::sync_with_stdio(false); 235 #ifndef ONLINE_JUDGE 236 freopen("in.cpp", "r", stdin); 237 #endif 238 239 kase = 0; 240 int T; 241 scanf("%d", &T); 242 while (T--) 243 { 244 init(); 245 input(); 246 solve(); 247 output(); 248 } 249 return 0; 250 }