首页 > 代码库 > HDU4862-Jump（最大流量最大费用流）
HDU4862-Jump（最大流量最大费用流）
题意：有n*m的格子，每一个格子包含一个数字，0-9。你初始的能量为0，你可以玩k次，每一个你可以选择你现在的格子的正下方或者正右方的任意一个格子跳，但必须是之前没有跳过的格子。每玩一次你都可以跳任意次。每跳一次，从(x1, y1) 到 (x2, y2)，你将花费|x1-x2|+|y1-y2|-1的能量，如果起止格子的数字相同，你能获得格子里数字的能量。
问你在把每一个格子都经过的基础上，所能得到的最大能量。
每个格子只能经过一个，你可以跳少于k次。你的能量可以为负数。
>>之前做过成环覆盖所有点的题，拆点建立二分图，此题和那个题感觉有点像。
建图的方法就是源点连所有X部，流量为1，权值为0，所有Y部连汇点，流量是1，权值为0。
能够从a点走到b点，就从a的X部到b的Y部，权值就是花费。
然后在X部添加一个点Q，从源点连到Q流量为k，权值为0的边，Q到Y部每一个点都连流量为1，权值为0的边，来保证玩k次。
最后求一个最大流量最大费用就好了。
>>建图很巧妙，但是。。。不是很懂。。。。先记下方法了。。。
#include <algorithm>#include <iostream>#include <cstring>#include <string>#include <vector>#include <bitset>#include <cstdio>#include <queue>#include <stack>#include <cmath>#include <list>#include <map>#include <set>#define pk(x) printf("%d\n", x)using namespace std;#define PI acos(-1.0)#define EPS 1E-6#define clr(x,c) memset(x,c,sizeof(x))//#pragma comment(linker, "/STACK:102400000,102400000")typedef long long ll;#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int MAXV = 410;const int INF = 1<<30;struct Edge { int to, cap, cost, rev; };vector<Edge> G[MAXV];int dist[MAXV], prv[MAXV], pre[MAXV], in[MAXV];queue<int> que;void addedge(int from, int to, int cap, int cost) { G[from].push_back((Edge){to, cap, cost, G[to].size()}); G[to].push_back((Edge){from, 0, -cost, G[from].size()-1});}int min_cost_max_flow(int s, int t, int f) { int res = 0; while (f > 0) { for (int i = 0; i <= t; ++i) dist[i] = -INF, in[i] = 0; dist[s] = 0; while (!que.empty()) que.pop(); in[s] = 1; que.push(s); while (!que.empty()) { int u = que.front(); que.pop(); in[u] = 0; for (int i = 0; i < G[u].size(); ++i) { Edge &e = G[u][i]; if (e.cap > 0 && dist[e.to] < dist[u] + e.cost) { dist[e.to] = dist[u] + e.cost; prv[e.to] = u; pre[e.to] = i; if (in[e.to] == 0) { in[e.to] = 1; que.push(e.to); } } } } if (dist[t] == -INF) return -1; int d = f; for (int v = t; v != s; v = prv[v]) { d = min(d, G[prv[v]][pre[v]].cap); } f -= d; res += d * dist[t]; for (int v = t; v != s; v = prv[v]) { Edge &e = G[prv[v]][pre[v]]; e.cap -= d; G[v][e.rev].cap += d; } } return res;}int n, m, k;char str[15][15];int id1(int x, int y) { return x*m+y+1;}int id2(int x, int y) { return n*m+x*m+y+1;}// |x1-x2|+|y1-y2|-1int cost(int x1, int y1, int x2, int y2) { int ans = -(abs(x1-x2)+abs(y1-y2)-1); if (str[x1][y1] == str[x2][y2]) ans += str[x1][y1] - ‘0‘; return ans;}int main(){ int T, cas = 0; scanf("%d", &T); while (T--) { scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < n; ++i) { scanf("%s", str[i]); } int src = http://www.mamicode.com/0; int q = n*m*2+1; int sink = n*m*2+2; for (int i = src; i <= sink; ++i) G[i].clear(); addedge(src, q, k, 0); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { addedge(src, id1(i, j), 1, 0); addedge(id2(i,j), sink, 1, 0); addedge(q, id2(i,j), 1, 0); for (int k = i+1; k < n; ++k) { addedge(id1(i, j), id2(k, j), 1, cost(i,j,k,j)); } for (int k = j+1; k < m; ++k) { addedge(id1(i,j), id2(i,k), 1, cost(i,j,i,k)); } } } printf("Case %d : %d\n", ++cas, min_cost_max_flow(src, sink, n*m)); } return 0;}
HDU4862-Jump（最大流量最大费用流）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。