洛谷P4009骑车加油行驶问题（分层图、最小费用最大流）

骑车加油行驶问题（分层图、最小费用最大流）"/>

洛谷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;
}