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 
    
     #define fi first#define se second#define pii pair
     
      #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 ivorysiusing namespace std;typedef long long int64;typedef unsigned int u32;typedef double db;template 
      
       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 
       
        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
        
          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();}