[HDU][ACM]4862 Jump
海胖子 - 2014/07/23最小K路径覆盖的模型,用费用流或者KM算法解决,构造二部图,X部有N*M个节点,源点向X部每个节点连一条边,流量1,费用0,Y部有N*M个节点,每个节点向汇点连一条边,流量1,费用0,如果X部的节点x可以在一步之内到达Y部的节点y,那么就连边x->y,费用为从x格子到y格子的花费能量减去得到的能量,流量1,再在X部增加一个新的节点,表示可以从任意节点出发K次,源点向其连边,费用0,流量K,这个点向Y部每个点连边,费用0,流量1,最这个图跑最小费用最大流,如果满流就是存在解,反之不存在,最小费用的相反数就是可以获得的最大能量。
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4862
题解来自:http://blog.sina.com.cn/s/blog_6bddecdc0102uy9g.html
/* * Author: Haipz * School: HDU * File Name: 4862.cpp */ #include <cstdio> #include <cmath> #include <ctime> #include <cctype> #include <cfloat> #include <cstdlib> #include <cstring> #include <climits> #include <iostream> #include <vector> #include <string> #include <stack> #include <queue> #include <set> #include <map> #include <algorithm> using namespace std; const int T = 100, N = 10, M = 10, K = 100; char mat[N + 5][M + 5]; struct node { int x, y; void insert(int tx, int ty) { x = tx, y = ty; return; } } H[N*M*2 + 5], G[N*M*2 + 5]; struct edge { int u, v, cap, cost; edge *net, *opt; void insert(int tu, int tv, int tcap, int tcost, edge *tnet) { u = tu, v = tv, cap = tcap, cost = tcost, net = tnet; return; } } f[N*M*N*M*2 + 5], *link[N*M*2 + 5], *pre[N*M*2 + 5]; int dis[N*M*2 + 5]; bool vis[N*M*2 + 5]; queue<int> Q; void addEdge(int &num, int u, int v, int cap, int cost) { f[++num].insert(u, v, cap, cost, link[u]), link[u] = &f[num], f[num].opt = &f[num + 1]; f[++num].insert(v, u, 0, -cost, link[v]), link[v] = &f[num], f[num].opt = &f[num - 1]; return; } bool SPFA(int s, int t, int n) { while (!Q.empty()) Q.pop(); memset(vis, false, sizeof(vis)); memset(pre, 0, sizeof(pre)); fill(dis, dis + n, INT_MAX - 100); vis[s] = true, dis[s] = 0, Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(), vis[u] = false; for (edge *p = link[u]; p; p = p->net) { if (p->cap && dis[u] < dis[p->v] - p->cost) { dis[p->v] = dis[u] + p->cost, pre[p->v] = p; if (!vis[p->v]) Q.push(p->v), vis[p->v] = true; } } } if (dis[t] == INT_MAX - 100) return false; return true; } void MCMF(int &mincost, int &sumflow, int s, int t, int n) { mincost = 0, sumflow = 0; while (SPFA(s, t, n)) { int minflow = INT_MAX - 99; for (edge *p = pre[t]; p; p = pre[p->u]) minflow = min(minflow, p->cap); for (edge *p = pre[t]; p; p = pre[p->u]) p->cap -= minflow, p->opt->cap += minflow; sumflow += minflow, mincost += dis[t]*minflow; } return; } int main() { int t, ics = 0; scanf("%d", &t); while (t--) { memset(link, 0, sizeof(link)); int n, m, k; scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < n; ++i) scanf("%s", mat[i]); int num = 0; addEdge(num, 0, 1, k, 0); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { addEdge(num, 0, i*m + j + 2, 1, 0); for (int r = i + 1; r < n; ++r) { int energy = r - i - 1; if (mat[i][j] == mat[r][j]) energy -= mat[i][j] - '0'; addEdge(num, i*m + j + 2, n*m + r*m + j + 2, 1, energy); } for (int c = j + 1; c < m; ++c) { int energy = c - j - 1; if (mat[i][j] == mat[i][c]) energy -= mat[i][j] - '0'; addEdge(num, i*m + j + 2, n*m + i*m + c + 2, 1, energy); } addEdge(num, n*m + i*m + j + 2, n*m*2 + 2, 1, 0); addEdge(num, 1, n*m + i*m + j + 2, 1, 0); } int mincost, sumflow; MCMF(mincost, sumflow, 0, n*m*2 + 2, n*m*2 + 3); printf("Case %d : ", ++ics); if (sumflow == n*m) printf("%d\n", -mincost); else printf("-1\n"); } return 0; }
转载保留版权:http://haipz.com/blog/i/5321 - 海胖博客