HDU 4862 Jump

题意：给定一个N*M的矩阵，矩阵里面为0~9的数字。现在规定从一个点可以跳到它正下方和正右方的点，花费的费用为曼哈顿距离 - 1。如果在跳的过程中，两个点的数字相同，那么将得到该点的数字。规定可以从任意点开始跳，每个点只能经过1次。最多可以选择K个点来作为起点进行跳跃。问能否经过所有的点，如果可以，那么花费的费用是多少。

思路：

如果是最小路径覆盖，那么很容易构造图。但这里还有个限制是要在K次走完所有的点。

最小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，最后用这个图跑最小费用最大流，如果满流就是存在解，反之不存在，最小费用的相反数就是可以获得的最大能量。

代码：

/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include

#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define INF (1 << 30) #define LINF (1LL << 60) #define PI acos(-1.0) #define mem(a, b) memset(a, b, sizeof(a)) #define rep(i, a, n) for (int i = a; i < n; i++) #define per(i, a, n) for (int i = n - 1; i >= a; i--) #define eps 1e-6 #define debug puts(===============) #define pb push_back #define mkp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) #define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m) typedef long long ll; typedef unsigned long long ULL; int N, M, K; char mp[15][15]; const int maxn = 555; const int maxm = 5000; struct node { int v, cap, nxt, cost; } e[maxm * 2]; int g[maxn], cnt, st, ed, n, m; int ans, flow; void add(int u, int v, int cap, int cost) { e[++cnt].v = v; e[cnt].cap = cap; e[cnt].cost = cost; e[cnt].nxt = g[u]; g[u] = cnt; e[++cnt].v = u; e[cnt].cap = 0; e[cnt].cost = -cost; e[cnt].nxt = g[v]; g[v] = cnt; } void init() { cnt = 1; ans = flow = 0; st = N * M * 2; ed = st + 1; memset(g, 0, sizeof(g)); // 加边 n = N * M; int tmp = ed + 1; add(st, tmp, K, 0); //最小K路径覆盖需要另外构造一个点，从汇点连流量为K的边 for (int i = 0; i < n; i++) { add(st, i, 1, 0); // add(i + n, ed, 1, 0); add(tmp, i + n, 1, 0); } int c; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { int now = i * M + j; for (int l = i + 1; l < N; l++) { c = l - i - 1; if (mp[i][j] == mp[l][j]) c -= (mp[i][j] -'0'); add(now, l * M + j + n, 1, c); } for (int l = j + 1; l < M; l++) { c = l - j - 1; if (mp[i][j] == mp[i][l]) c -= (mp[i][j] - '0'); add(now, i * M + l + n, 1, c); } } } n = tmp; } int dis[maxn], que[maxn], pre[maxn]; bool vis[maxn]; bool spfa() { int font = 0, rear = 1; for(int i = 0; i <= n; i ++) { dis[i] = INF; vis[i] = false; } dis[st] = 0; que[0] = st; vis[st] = true; while(rear != font) { int u = que[font++]; font %= n; vis[u] = false; for(int i = g[u]; i; i = e[i].nxt) { int v = e[i].v; if(e[i].cap && dis[v] > dis[u] + e[i].cost) { dis[v] = dis[u] + e[i].cost; pre[v] = i; if(!vis[v]) { vis[v] = true; que[rear++] = v; rear %= n; } } } } if(dis[ed] == INF) return false; return true; } void augment() { int u, p, mi = INF; for(u = ed; u != st; u = e[p ^ 1].v) { p = pre[u]; mi = min(mi, e[p].cap); } for(u = ed; u != st; u = e[p ^ 1].v) { p = pre[u]; e[p].cap -= mi; e[p ^ 1].cap += mi; ans += mi * e[p].cost; // cost记录的为单位流量费用，必须得乘以流量。 } flow += mi; } int MCMF() { init(); while(spfa()) augment(); if (flow != N * M) return -1; return -ans; } int main () { int T, cas = 1; scanf(%d, &T); while(T--) { scanf(%d%d%d, &N, &M, &K); for (int i = 0; i < N; i++) scanf(%s, mp[i]); int dd = MCMF(); printf(Case %d : %d , cas++, dd); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu5019Revenge of GCD（枚举+gcd..	下一篇：HDU 2045 不容易系列之(3)―― LE..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: