洛谷 P4009 骑车加油行驶问题
题目链接 https://www.luogu.org/problem/P4009
建一个 \(k+1\) 层的图, 第 0 层为到加油站, 第 \(i\) \((1\leq i \leq k)\) 层为走了 \(i\) 步, 每个点向下一层中与它四联通的点建流量为 1 花费为 0 的边. 需要注意它只要经过加油站就必须要加油, 所以在 1 到 k 层中, 加油站的点只能向第 0 层建边, 不可向下一层建边
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 300100;
- const int maxm = 3000100;
- const int inf = 0x3f3f3f3f;
- typedef long long ll;
- struct edge {
- int to, next, cap, flow, cost;
- } e[maxm];
- int head[maxn], tot;
- int pre[maxn], dis[maxn];
- bool vis[maxn];
- int N;
- void init(int n) {
- N = n;
- tot = 1;
- memset(head, 0, sizeof(head));
- }
- void addedge(int u, int v, int cap, int cost) {
- e[++tot].to = v, e[tot].next = head[u], e[tot].cap = cap, e[tot].cost = cost, e[tot].flow = 0, head[u] = tot;
- e[++tot].to = u, e[tot].next = head[v], e[tot].cap = 0, e[tot].flow = 0, e[tot].cost = -cost, head[v] = tot;
- }
- bool spfa(int s, int t) {
- deque<int> q;
- for (int i = 0; i <= N; ++i) {
- dis[i] = inf;
- vis[i] = false;
- pre[i] = -1;
- }
- dis[s] = 0;
- vis[s] = true;
- q.push_front(s);
- while (!q.empty()) {
- int u = q.front();
- q.pop_front();
- vis[u] = 0;
- for (int i = head[u]; i; i = e[i].next) {
- int v = e[i].to;
- if (e[i].cap> e[i].flow && dis[v]> dis[u] + e[i].cost) {
- dis[v] = dis[u] + e[i].cost;
- pre[v] = i;
- if (!vis[v]) {
- vis[v] = true;
- if (!q.empty()) {
- if (dis[v] <dis[q.front()]) q.push_front(v);
- else q.push_back(v);
- } else q.push_back(v);
- }
- }
- }
- }
- return pre[t] != -1;
- }
- //return 最大流, cost 为最小费用
- int mcfc(int s, int t, ll &cost) {
- cost = 0;
- int flow = 0;
- while (spfa(s, t)) {
- int minn = inf;
- for (int i = pre[t]; i != -1; i = pre[e[i ^ 1].to]) {
- if (minn> e[i].cap - e[i].flow) {
- minn = e[i].cap - e[i].flow;
- }
- }
- for (int i = pre[t]; i != -1; i = pre[e[i ^ 1].to]) {
- e[i].flow += minn;
- e[i ^ 1].flow -= minn;
- cost += 1ll * e[i].cost * minn;
- }
- flow += minn;
- }
- return flow;
- }
- int mp[200][200];
- int n;
- inline int getid(int deep, int i, int j) {
- return deep * n * n + (i - 1) * n + j;
- }
- int main() {
- // freopen("in.txt", "r", stdin);
- int k, A, B, C;
- scanf("%d %d %d %d %d", &n, &k, &A, &B, &C);
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= n; j++) {
- scanf("%d", &mp[i][j]);
- }
- }
- int s = 0, t = getid(k + 1, 1, 1);
- init(t + 1);
- addedge(s, getid(0, 1, 1), 1, 0);
- for (int deep = 0; deep <= k; deep++) {
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= n; j++) {
- if (mp[i][j] && deep) {
- addedge(getid(deep, i, j), getid(0, i, j), 1, A);
- continue;
- }
- if (deep <k) {
- if (j + 1 <= n)
- addedge(getid(deep, i, j), getid(deep + 1, i, j + 1), 1, 0);
- if (i + 1 <= n)
- addedge(getid(deep, i, j), getid(deep + 1, i + 1, j), 1, 0);
- if (j - 1>= 1)
- addedge(getid(deep, i, j), getid(deep + 1, i, j - 1), 1, B);
- if (i - 1>= 1)
- addedge(getid(deep, i, j), getid(deep + 1, i - 1, j), 1, B);
- }
- int cost;
- if (deep == 0) continue;
- if (mp[i][j])cost = A;
- else cost = C + A;
- addedge(getid(deep, i, j), getid(0, i, j), 1, cost);
- }
- }
- addedge(getid(deep, n, n), t, 1, 0);
- }
- ll ans = 0;
- mcfc(s, t, ans);
- printf("%lld\n", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3191777.html