LOJ#3097. 「SNOI2019」通信
费用流，有点玄妙
显然按照最小路径覆盖那题的建图思路，把一个点拆成两种点，一种是从这个点出去，标成\(x_{i}\)，一种是输入到这个点，使得两条路径合成一条（或者是新建一条），标成\(y_i\)
源点向每个\(x_i\)流一条容量为1，费用为0的边
然后向每个\(y_{i}\)流一条容量为1，费用为W的边
每个\(y_i\)向汇点连一条容量为1，费用为0的边
这个时候，如果你充满梦想，你可以把所有的\(x_{i}\)到\(y_j\)(\(i < j\))连一条\(|a_{i} - a_{j}|\)的边
然而你没有梦想，你觉得似乎不太优秀
然后你可以分治，把每一层的点分成左右两部分，然后把左边点权值离散化后建出一个前缀最大值节点，串成一条链，并在对应的位置连上左边的\(a_{i}\)
另一种情况把右边的权值离散化（或者按相同的方式给左边连负数也行），建出前缀最大值节点，串成一条链，在对应位置连上右边的\(a_{i}\)
这样边数就被优化成\(n\log n\)了
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define ba 47
#define MAXN 1005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template <class T>
void read(T &res) {
res = 0;
T f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template <class T>
void out(T x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
struct node {
int to, next, cap;
int64 val;
} E[3000005];
int head[2000005], sumE = 1;
int x[1005], y[1005], N, a[1005], W, S, T, Ncnt = 0;
void add(int u, int v, int c, int64 a) {
E[++sumE].to = v;
E[sumE].next = head[u];
E[sumE].cap = c;
E[sumE].val = a;
head[u] = sumE;
}
void addtwo(int u, int v, int c, int64 a) {
add(u, v, c, a);
add(v, u, 0, -a);
}
int val[1005], tot, pos[1005];
void build(int l, int r) {
if (l == r)
return;
if (r - l + 1 == 2) {
addtwo(x[l], y[r], 1, abs(a[l] - a[r]));
return;
}
int mid = (l + r) >> 1;
build(l, mid);
build(mid + 1, r);
tot = 0;
for (int i = l; i <= mid; ++i) {
val[++tot] = a[i];
}
sort(val + 1, val + tot + 1);
tot = unique(val + 1, val + tot + 1) - val - 1;
for (int i = tot; i >= 1; --i) {
pos[i] = ++Ncnt;
if (i != tot)
addtwo(pos[i + 1], pos[i], 1e9, 0);
}
for (int i = l; i <= mid; ++i) {
int t = lower_bound(val + 1, val + tot + 1, a[i]) - val;
addtwo(x[i], pos[t], 1, a[i]);
}
for (int i = mid + 1; i <= r; ++i) {
int t = lower_bound(val + 1, val + tot + 1, a[i]) - val;
if (t <= tot)
addtwo(pos[t], y[i], 1, -a[i]);
}
tot = 0;
for (int i = mid + 1; i <= r; ++i) val[++tot] = a[i];
sort(val + 1, val + tot + 1);
tot = unique(val + 1, val + tot + 1) - val - 1;
for (int i = 1; i <= tot; ++i) {
pos[i] = ++Ncnt;
if (i != 1)
addtwo(pos[i - 1], pos[i], 1e9, 0);
}
for (int i = mid + 1; i <= r; ++i) {
int t = lower_bound(val + 1, val + tot + 1, a[i]) - val;
addtwo(pos[t], y[i], 1, a[i]);
}
for (int i = l; i <= mid; ++i) {
int t = lower_bound(val + 1, val + tot + 1, a[i]) - val;
if (t <= tot)
addtwo(x[i], pos[t], 1, -a[i]);
}
}
int64 dis[100005];
int preE[100005];
bool inq[100005];
queue<int> Q;
bool SPFA() {
for (int i = 1; i <= Ncnt; ++i) dis[i] = 1e18;
memset(inq, 0, sizeof(inq));
inq[S] = 1;
dis[S] = 0;
Q.push(S);
while (!Q.empty()) {
int u = Q.front();
Q.pop();
inq[u] = 0;
for (int i = head[u]; i; i = E[i].next) {
if (E[i].cap > 0) {
int v = E[i].to;
if (dis[v] > dis[u] + E[i].val) {
dis[v] = dis[u] + E[i].val;
preE[v] = i;
if (!inq[v]) {
inq[v] = 1;
Q.push(v);
}
}
}
}
}
return dis[T] != 1e18;
}
void Init() {
read(N);
read(W);
S = 2 * N + 1, T = 2 * N + 2;
for (int i = 1; i <= N; ++i) {
read(a[i]);
x[i] = ++Ncnt;
y[i] = ++Ncnt;
addtwo(S, x[i], 1, 0);
addtwo(S, y[i], 1, W);
addtwo(y[i], T, 1, 0);
}
Ncnt += 2;
build(1, N);
}
void Solve() {
Init();
int64 ans = 0;
while (SPFA()) {
ans += dis[T];
int p = T;
while (p != S) {
int t = preE[p];
E[t].cap -= 1;
E[t ^ 1].cap += 1;
p = E[t ^ 1].to;
}
}
out(ans);
enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in", "r", stdin);
#endif
Solve();
}