首页 > 代码库 > POJ 3422 Kaka's Matrix Travels (最小费用最大流)
POJ 3422 Kaka's Matrix Travels (最小费用最大流)
POJ 3422 Kaka‘s Matrix Travels
链接:http://poj.org/problem?id=3422
题意:有一个N*N的方格,每个方格里面有一个数字。现在卡卡要从左上角走到右下角,规定每次只能向下或者向右走,每次走到一个格子,将得到该格子的数字,并且该格子的数字变为0。当卡卡走一次时,很容易求出最大值,问卡卡走k次,能够得到的最大值为多少。
思路:最小费用最大流
关键是如何构图
1. 将N*N个格点拆分为两个点(i,i + N*N),每个点之间连一条流量为1,费用为-w的边,再连一条流量为k,费用为0的边。这样就保证了每个点之间可以走k次,且最多只有一次能拿到费用。
2. 将每个点与其下面、右边的点连边,流量为k,费用为0.
3. 构造两个源点、汇点。源点和左上角连边,流量为k,费用为0. 右下角与汇点连边,流量为k,费用为0.
至此,容量网络已经构成。 每次在残余网络中找费用最短路进行增广即可。
代码:
/* ID: wuqi9395@126.com PROG: LANG: C++ */ #include<map> #include<set> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<fstream> #include<cstring> #include<ctype.h> #include<iostream> #include<algorithm> using namespace std; #define INF (1 << 20) #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; const int maxn = 5555; const int maxm = 500000; struct node { int v, cap, nxt, cost; } e[maxm * 2]; int g[maxn], cnt, st, ed, n, m; int ans, flow; int nt, k; 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; memset(g, 0, sizeof(g)); // 加边 int w; int p = nt * nt; for (int i = 1; i <= nt; i++) { for (int j = 1; j <= nt; j++) { scanf("%d", &w); int id = (i - 1) * nt + j; add(id, id + p, 1, -w); add(id, id + p, k, 0); if (i < nt) add(id + p, id + nt, k, 0); if (j < nt) add(id + p, id + 1, k, 0); } } st = 0, ed = p * 2 + 1; n = ed; add(st, 1, k, 0); add(p * 2, ed, k, 0); } 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(); return ans; } int main () { while(~scanf("%d%d", &nt, &k)) { printf("%d\n", -MCMF()); } return 0; }
POJ 3422 Kaka's Matrix Travels (最小费用最大流)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。