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();

}

巴特西

【LOJ】#3097. 「SNOI2019」通信

LOJ#3097. 「SNOI2019」通信

最新文章

热门文章