Kaka's Matrix poj3422 费用流

Description

---

给定n*n的矩阵，求从起点走到终点走k次的最大路径权的和，每个点能多次走但只能获取1次值

Solution

---

好气啊数组开错了wa好久，第几次了都

题目和3680相比有改变，那么我们仍然拆点，然后入点和出点连一条容量INF费用0的边，就能保证点能重复走且权值只拿一次

Code

---

#include <stdio.h> #include <string.h> #include <queue> #define rep(i, st, ed) for (int i = st; i <= ed; i += 1) #define erg(i, st) for (int i = ls[st]; i; i = e[i].next) #define fill(x, t) memset(x, t, sizeof(x)) #define INF 0x3f3f3f3f #define L 505 #define N 100001 #define E 100001 struct edge{int x, y, w, c, next;}e[E]; int ls[N]; inline void addEdge(int &cnt, int x, int y, int w, int c){ cnt += 1; e[cnt] = (edge){x, y, w, c, ls[x]}; ls[x] = cnt; cnt += 1; e[cnt] = (edge){y, x, 0, -c, ls[y]}; ls[y] = cnt; } using std:: queue; int inQueue[N], dis[N], pre[N]; inline int spfa(int st, int ed){ queue<int> que; que.push(st); rep(i, st, ed){ dis[i] = -INF; inQueue[i] = 0; } dis[st] = 0; inQueue[st] = 1; while (!que.empty()){ int now = que.front(); que.pop(); erg(i, now){ if (e[i].w > 0 && dis[now] + e[i].c > dis[e[i].y]){ dis[e[i].y] = dis[now] + e[i].c; pre[e[i].y] = i; if (!inQueue[e[i].y]){ inQueue[e[i].y] = 1; que.push(e[i].y); } } } inQueue[now] = 0; } return dis[ed] != -INF; } inline int min(int x, int y){ return x<y?x:y; } inline int modify(int ed){ int mn = INF, ret = 0; for (int i = ed; pre[i]; i = e[pre[i]].x){ mn = min(mn, e[pre[i]].w); ret += e[pre[i]].c; } for (int i = ed; pre[i]; i = e[pre[i]].x){ e[pre[i]].w -= mn; e[pre[i] ^ 1].w += mn; } return ret * mn; } inline int mcf(int st, int ed){ int tot = 0; while (spfa(st, ed)){ tot += modify(ed); } return tot; } int rc[L][L]; int main(void){ int n, k; while (scanf("%d%d", &n, &k) != EOF){ rep(i, 1, n){ rep(j, 1, n){ scanf("%d", &rc[i][j]); } } fill(ls, 0); int edgeCnt = 1; int lim = n * n; int st = 0, ed = lim + lim + 1; rep(i, 1, n){ rep(j, 1, n){ int x = i * n - n + j; if (i < n){ int y = i * n + j; addEdge(edgeCnt, x + lim, y, INF, 0); } if (j < n){ int y = i * n - n + j + 1; addEdge(edgeCnt, x + lim, y, INF, 0); } addEdge(edgeCnt, x, x + lim, 1, rc[i][j]); addEdge(edgeCnt, x, x + lim, INF, 0); } } addEdge(edgeCnt, st, 1, k, 0); addEdge(edgeCnt, lim + lim, ed, k, 0); int ans = mcf(st, ed); printf("%d\n", ans); } return 0; }