백준14904 이동하기 2

작성일 | In

문제 링크

  • http://icpc.me/14904

사용 알고리즘

  • MCMF

풀이

일단 정점 분할을 합시다.
분할한 정점 사이에 용량이 1이고 비용이 사탕 개수인 간선을 추가해주고, 사탕을 먹은 이후에도 유량이 흐를 수 있도록 용량이 K-1, 비용이 0인 간선도 추가를 해줍시다.
오른쪽 혹은 아래로 이동할 수 있으므로 적절히 간선을 잘 이어준 다음에 mcmf를 돌리면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n, k;

struct Edge {
	int v, dual, cap, dst;
	Edge() {}
	Edge(int v, int dual, int cap, int dst) : v(v), dual(dual), cap(cap), dst(dst) {}
};

vector<Edge> g[5050];

void addEdge(int s, int e, int x, int y) { //cap, dst
	g[s].emplace_back(e, g[e].size(), x, y);
	g[e].emplace_back(s, g[s].size() - 1, 0, -y);
}

int go(int s, int t) {
	int ret = 0;
	int tot = 0;
	while (1) {
		queue<int> q;
		vector<bool> inq(5050, 0);
		vector<int> dst(5050, 1e9 + 7);
		vector<int> par(5050, -1);
		vector<int> idx(5050, -1);
		q.push(s); inq[s] = 1; dst[s] = 0;
		while (q.size()) {
			int now = q.front(); q.pop(); inq[now] = 0;
			for (int x = 0; x < g[now].size(); x++) {
				Edge i = g[now][x];
				int nxt = i.v;
				int dual = i.dual;
				int cap = i.cap;
				int cst = i.dst;
				if (cap > 0 && dst[now] + cst < dst[nxt]) {
					dst[nxt] = dst[now] + cst; par[nxt] = now; idx[nxt] = x;
					if (!inq[nxt]) {
						inq[nxt] = 1; q.push(nxt);
					}
				}
			}
		}
		if (par[t] == -1) break;
		int fl = 1e9 + 7;
		for (int i = t; i != s; i = par[i]) {
			int a = par[i], b = idx[i];
			fl = min(fl, g[a][b].cap);
		}
		for (int i = t; i != s; i = par[i]) {
			int a = par[i], b = idx[i];
			ret += fl * g[a][b].dst;
			g[a][b].cap -= fl; g[i][g[a][b].dual].cap += fl;
		}
		tot += fl;
	}
	return ret;
}

int conv(int i, int j, bool flag) {
	int ret = i * n + j;
	if (flag) return ret << 1;
	else return ret << 1 | 1;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int x; cin >> x;
			addEdge(conv(i, j, 1), conv(i, j, 0), 1, -x);
			addEdge(conv(i, j, 1), conv(i, j, 0), k - 1, 0);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i + 1 < n) addEdge(conv(i, j, 0), conv(i + 1, j, 1), k, 0);
			if (j + 1 < n) addEdge(conv(i, j, 0), conv(i, j + 1, 1), k, 0);
		}
	}
	cout << -go(conv(0, 0, 1), conv(n-1, n-1, 0));
}