P4553 80人环游世界 题解
sangshang
·
·
题解
Description
对于每个人的路线，可以在任意位置开始，任意位置结束，但途经节点编号单调递增。两个城市间移动有固定费用，也有可能不连通。保证有解，求最小花费。
# Solution
考虑不同路径，任意起点终点，人流量一定，和费用最小，可以确定是费用流模型。注意具体的，因为点的出入人流量一定，所以考虑**有源汇上下界最小费用可行流**。
为了保证每个点贡献唯一，将每个点拆成入点和出点，从入点向出点连一条边，表示经过该城市。像这样，流量从入点进入，全部途经向出点的连边，保证贡献唯一。为保证人流流量一定，对于一个点拆成的两点，从出点到汇点的连边是一条上下界均为 $V_i$ 费用为 $0$ 的边。
虚拟源汇点，表示有 $m$ 个人旅游。因为旅游人数一定，所以所以新建立两点，将源汇点也拆成两点，入点到出点的连边是一条上下界均为 $m$ 费用为 $0$ 的边。并从源点的出点向每个城市的入点连下界为 $0$ 上界为 $+\infty$ 费用为 $0$ 的边。汇点同理。
对于一条从城市 $i$ 到城市 $j$ 费用为 $cost$ 的边，从 $i$ 的出点向 $j$ 的入点连一条下界为 $0$ 上界为 $+\infty$ 费用为 $cost$ 的边。表示经过点 $i$ 流向点 $j$。
## 有源汇上下界最小费用可行流
如果不会上下界网络流看[这道题](https://www.luogu.com.cn/problem/P5192)。
将最大流改成费用流也是一个道理，边的费用不变，先将边的下界流满，注意预先累加费用。
再虚拟超级源汇点，将流量不平衡的边与超级源汇点对应连边，意为根据每条边剩余可调整流量将流量调整平衡。
上述两步费用累加起来，就是可行流最小费用。
## C++ Code
```cpp
#include <bits/stdc++.h>
using namespace std;
class Dinic {
public:
typedef int TYPE;
static const int maxn = 1e4, inf = 0x7f7f7f7f, maxm = inf;
class edge {
public:
int to, rev;
TYPE flow, cost;
edge(int to, TYPE flow, TYPE cost, int rev): to(to), flow(flow), cost(cost), rev(rev) {}
edge() {}
};
std::vector<edge>vec[maxn];
TYPE MinCost, MaxFlow, dist[maxn], W[maxn];
int cur[maxn], n, m, s, t;
bool vis[maxn];
Dinic(int n, int m, int s, int t): n(n), m(m), s(s), t(t),
MinCost(0), MaxFlow(0), cur({0}), dist({0}), vis({false}) {}
Dinic() {}
inline void _Add_Edge_(int from, int to, TYPE flow, TYPE cost) {
vec[from].push_back(edge(to, flow, cost, vec[to].size()));
vec[to].push_back(edge(from, 0, -cost, vec[from].size() - 1));
}
inline void Add_Edge(int from, int to, TYPE flowL, TYPE flowR, TYPE cost) {
W[from] -= flowL, W[to] += flowL;
MinCost += flowL * cost;
_Add_Edge_(from, to, flowR - flowL, cost);
}
inline bool SPFA() {
std::memset(dist, inf, sizeof(dist));
dist[t] = 0;
std::memset(cur, 0, sizeof(cur));
std::queue<int>que;
for (que.push(t), vis[t] = true; !((bool) que.empty());) {
int u = que.front();
vis[u] = false;
que.pop();
for (edge &e : vec[u]) {
int v = e.to;
if (vec[v][e.rev].flow && dist[u] + vec[v][e.rev].cost < dist[v]) {
dist[v] = dist[u] + vec[v][e.rev].cost;
if (!vis[v]) {
que.push(v);
vis[v] = true;
}
}
}
}
return dist[s] != inf;
}
inline TYPE dfs(int u, TYPE flow) {
if (u == t || !flow) {
return flow;
}
vis[u] = true;
TYPE res = 0;
int sz = vec[u].size();
for (int &i = cur[u]; i < sz && flow; ++i) {
edge &e = vec[u][i];
int v = e.to;
if (e.flow && dist[u] == dist[v] + e.cost && !vis[v]) {
TYPE Preflow = dfs(v, std::min(flow, e.flow));
res += Preflow, flow -= Preflow, MinCost += Preflow * (e.cost);
e.flow -= Preflow, vec[v][e.rev].flow += Preflow;
}
}
vis[u] = false;
return res;
}
inline TYPE Get_MaxFlow_MinCost() {
MaxFlow = 0;
while (SPFA()) {
std::memset(vis, false, sizeof(vis));
TYPE Preflow = dfs(s, inf);
MaxFlow += Preflow;
}
return MaxFlow;
}
inline TYPE clac(int S, int T) {
Add_Edge(T, S, 0, inf, 0);
int PreS = n + 1, PreT = n + 2;
this->s = PreS, this->t = PreT;
TYPE sum = 0;
for (int i = 0; i <= n; ++i) {
if (W[i] > 0) {
Add_Edge(PreS, i, 0, W[i], 0);
sum += W[i];
} else if (W[i] < 0) {
Add_Edge(i, PreT, 0, -W[i], 0);
}
}
if (Get_MaxFlow_MinCost() < sum) {
return -1;
} else {
return (MaxFlow = vec[S].back().flow);
}
}
inline void Solve() {
#define id(a,CLASS) (a+(CLASS*N))
int N, M;
scanf("%d%d", &N, &M);
this[0] = Dinic(N * 2 + 5, inf, N * 2 + 1, N * 2 + 2);
for (int i = 1; i <= N; ++i) {
int tmp;
scanf("%d", &tmp);
Add_Edge(id(i, 0), id(i, 1), tmp, tmp, 0);
}
for (int i = 1; i < N; ++i) {
for (int j = i + 1; j <= N; ++j) {
int tmp;
scanf("%d", &tmp);
if (tmp != -1) {
Add_Edge(id(i, 1), id(j, 0), 0, inf, tmp);
}
}
}
int LimS = N * 2 + 3, LimT = N * 2 + 4;
Add_Edge(s, LimS, M, M, 0);
Add_Edge(LimT, t, M, M, 0);
for (int i = 1; i <= N; ++i) {
Add_Edge(LimS, id(i, 0), 0, inf, 0);
Add_Edge(id(i, 1), LimT, 0, inf, 0);
}
TYPE Ans = clac(s, t);
if (~Ans) {
printf("%d\n", MinCost);
} else {
printf("No Solution.%d\n", MinCost);
}
}
};
Dinic Main;
int main() {
Main.Solve();
return 0;
}
```