P5331 [SNOI2019]通信

P5331 SNOI2019通信

前言：

我省去年省选题。
拿到的时候直接想了个80分做法（震惊，暴力80分，不过去年好像进队要325分，，，）。
然后同机房聚铑教了满分做法，以为自己理解了，发现理解错了。

核心思想

连边方式：拆 (i) 点为 (i_1, i_2)，建立源点，汇点 (S, T)。

80分暴力连边方式：
(S ightarrow i_1) 费用0， 流量1
(i_1 ightarrow T) 费用W， 流量1
(i_2 ightarrow T) 费用0， 流量1
然后 (i_1) 向前面所有的 (j_2) 连边，费用 (mid a_i - a_j mid) 流量1

正解连边：

利用cdq分治优化建图（主席树啥的随便写，我懒）
简单来说就是保证下标大的只能连下标小的，那么考虑区间 ([l, r])（下标区间） 其中 ([mid+1, r]) 的一段必定可以向 ([l, mid]) 的一段连边。那么我们将这段区间有的权值建立一条虚链，然后跑网络瘤就行。注意去重，离散化就行。

核心代码（我不信来写这道题的不会网络瘤）

void lk(ll l, ll r) {
    if (l == r) return;
    ll mid = (l+r)>>1, num = 0;
    lk(l, mid); lk(mid+1, r);
    for (ll i = l; i <= r; i++) b[++num] = x[i];
    std::sort(b+1, b+num+1); num = std::unique(b+1, b+num+1)-b-1;
    for (ll i = 1; i < num; i++) {
        add(tot+i, tot+i+1, INF, b[i+1]-b[i]);
        add(tot+i+1, tot+i, INF, b[i+1]-b[i]);
    }
    for (ll i = l; i <= r; i++) {
        ll pos = std::lower_bound(b+1, b+num+1, x[i]) - b;
        if (i > mid) add(p[i][0], tot+pos, 1, 0);
        else add(tot+pos, p[i][1], 1, 0);
    }
    tot += num;
}

全部代码（不建议抄袭）：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

typedef long long ll;
const ll MAXN = 8e5+10;
const ll INF = 0x3f3f3f3f3f3f3f3f;

struct edge {
    ll nt, to, v, f;
} E[MAXN];

ll N, W, x[MAXN], S, T, head[MAXN], cnt = -1, b[MAXN], tot = 0, p[MAXN][2], dis[MAXN], vis[MAXN], ans;

void add(ll, ll, ll, ll);
void adde(ll, ll, ll, ll);
ll dfs(ll, ll);
void lk(ll, ll);
bool spfa();

int main() {
    memset(head, -1, sizeof(head));
    scanf("%lld%lld", &N, &W);
    S = ++tot, T = ++tot;
    for (ll i = 1; i <= N; i++) {
        scanf("%lld", x+i);
        p[i][0] = ++tot;
        p[i][1] = ++tot;
    }
    for (ll i = 1; i <= N; i++) {
        add(S, p[i][0], 1, 0);
        add(p[i][0], T, 1, W);
        add(p[i][1], T, 1, 0);
    }
    lk(1, N);
    while (spfa()) {
        ans += dfs(S, INF) * dis[T];
    }
    printf("%lld
", ans);
    return 0;
}

bool spfa() {
    std::queue <ll> q;
    q.push(S);
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[S] = 0;
    vis[S] = 1;
    while (!q.empty()) {
        ll nt = q.front(); q.pop();
    	vis[nt] = 0;
        for (ll i = head[nt]; ~i; i = E[i].nt) {
            ll v = E[i].to;
            if (E[i].v && dis[v] > dis[nt] + E[i].f) {
                dis[v] = dis[nt] + E[i].f;
                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return dis[N] != INF;
}

ll dfs(ll n, ll flow) {
    if (n == T) return flow;
    ll used = 0;
    vis[n] = 1;
    for (ll i = head[n]; ~i; i = E[i].nt) {
        ll v = E[i].to;
        if (dis[v] == dis[n] + E[i].f && E[i].v && (!vis[v] || v == T)) {
            ll w = dfs(v, std::min(flow - used, E[i].v));
            used += w;
            E[i].v -= w;
            E[i^1].v += w;
            if (used == flow) return used;
        }
    }
    if (!used) dis[n] = 0;
    return used;
}

void lk(ll l, ll r) {
    if (l == r) return;
    ll mid = (l+r)>>1, num = 0;
    lk(l, mid); lk(mid+1, r);
    for (ll i = l; i <= r; i++) b[++num] = x[i];
    std::sort(b+1, b+num+1); num = std::unique(b+1, b+num+1)-b-1;
    for (ll i = 1; i < num; i++) {
        add(tot+i, tot+i+1, INF, b[i+1]-b[i]);
        add(tot+i+1, tot+i, INF, b[i+1]-b[i]);
    }
    for (ll i = l; i <= r; i++) {
        ll pos = std::lower_bound(b+1, b+num+1, x[i]) - b;
        if (i > mid) add(p[i][0], tot+pos, 1, 0);
        else add(tot+pos, p[i][1], 1, 0);
    }
    tot += num;
}

void add(ll x, ll y, ll v, ll f) {
    adde(x, y, v, f);
    adde(y, x, 0, -f);
}

void adde(ll x, ll y, ll v, ll f) {
    cnt++;
    E[cnt].to = y;
    E[cnt].nt = head[x];
    E[cnt].v = v;
    E[cnt].f = f;
    head[x] = cnt;
}