SOl p8461

考虑：

源点向每个开始区间 $i$ 连边，容量为 $1$ ，费用为 $a_i$ 。
每个开始区间 $i$ 向数轴上对应在区间 $[sl_i,sr_i]$ 的点连边，容量为 $1$ ，费用为 $0$ 。
数轴上的 $i$ 向 $i+1$ 连边，容量为 $1$ ，费用为 $1$ 。
数轴上每个在区间 $[el_j,er_j]$ 的点向对应结束区间 $j$ 连边，容量为 $1$ ，费用为 $0$ 。
每个结束区间 $j$ 向汇点连边，容量为 $1$ ，费用为 $b_j$ 。

建出来的网络流模型应该是这样的：

这样建图，一个开始区间

i

和结束区间

j

的匹配可被看作是源点到开始区间

i

对应点，再到数轴对应点，再到结束区间

j

对应点最后到汇点的增广路，其对答案贡献即为该增广路费用和。由于开始区间

i

，结束区间

j

的容量均为

1

，因此区间不会重复匹配。同样的，数轴上的容量也为

1

，所以子段不会重复覆盖一个数轴上区间。

跑最大费用最大流（把费用取相反数然后按照最小费用最大流做），复杂度

O(V\cdot E\cdot f)

，其中

V,E

是

10^3

级别的，应该比较难卡过去。

令「关键点」集合

S=\{sl_i\mid 1\le i\le m_1\}\cup \{sr_i\mid 1\le i\le m_1\}\cup \{el_i\mid 1\le i\le m_2\}\cup \{er_i\mid 1\le i\le m_2\}

，一个直观的贪心性质就是子段左右端点

S

中的点是最优的。

证明就是如果左端点选择了不属于

S

的点

l

，且

l

到其左侧最近属于

S

的点

t

的线段上没有其他的子段左右端点，则

l\gets t

是合法的，并且对于答案是更优的，只会增加了多覆盖的一段的长度的贡献。

如果

l

到其左侧最近属于

S

的点

t

的线段上有其他的子段左右端点

r

，则

l\gets t,r\gets t

是合法的，并且因为原本

r\sim l

的子段没有被覆盖现在被覆盖了，对于答案是不劣的。

右端点同理。

所以数轴上只需要保留

\in S

的点，

V,E

降到了

300

的级别，就可以过了。

CPP

struct Edge {
    int to, nxt, f; ll c;
} e[int (2e5) + 7];

void Addedge (int u, int v, int f, ll c) {
    ++ cnt;
    e[cnt].to = v, e[cnt].nxt = hd[u], e[cnt].f = f, e[cnt].c = c;

    hd[u] = cnt;
}

namespace SSP {
    int pre[N], vis[N];

    ll dis[N], f[N];

    int ans; ll cst;

    void Update () {
        ans += f[t], cst += dis[t] * f[t];
        int now = t;
        while (now != s) {
            int _ = pre[now];
            e[_].f -= f[t], e[_ ^ 1].f += f[t];
            now = e[_ ^ 1].to;
        }
    }
    
    int BF () {
        queue <int> q;

        q.push (s);

        F (i, 0, len) dis[rk[i]] = inf;
        F (i, 0, len) vis[rk[i]] = 0;
        dis[s] = 0ll;

        vis[s] = 1;

        f[s] = inf;

        while (! q.empty ()) {
            int u = q.front (); q.pop ();
            vis[u] = 0;
            for (int i = hd[u]; i != -1; i = e[i].nxt) {
                int v = e[i].to;
                ll fl = e[i].f, c = e[i].c;
                if (fl > 0 && c + dis[u] < dis[v]) {
                    dis[v] = c + dis[u];
                    f[v] = min (f[u], fl);
                    pre[v] = i;
                    if (! vis[v]) {
                        vis[v] = 1;
                        q.push (v);
                    }
                }
            }
        }

        return (dis[t] != inf);
    }

    void EK () {
        while (BF ()) {
            Update ();
        }
    }
}

#define AE(u,v,f,c) Addedge (u, v, f, c); Addedge (v, u, 0, -(c));

int main() {
    IOS
    cin >> n >> m1 >> m2;
    len = 2; rk[0] = s, rk[1] = t, rk[2] = _s;
    F (i, 0, N - 1) hd[i] = -1;
    F (i, 1, m1) cin >> sl[i] >> sr[i];
    F (i, 1, m2) cin >> el[i] >> er[i];

    F (i, 1, m1) qwq[++ _n] = sl[i]; F (i, 1, m1) qwq[++ _n] = sr[i];
    F (i, 1, m2) qwq[++ _n] = el[i]; F (i, 1, m2) qwq[++ _n] = er[i];

    sort (qwq + 1, qwq + _n + 1);

    F (i, 1, _n) mp[qwq[i]] = 1;

    F (i, 1, m1) cin >> a[i]; F (i, 1, m2) cin >> b[i];

    AE (s, _s, n, 0);

    F (i, 1, m1) {
        -- pos;
        AE (_s, pos, 1, -a[i]);
        rk[++ len] = pos;

        F (j, sl[i], sr[i]) 
            if (mp[j]) {AE (pos, j, 1, 0);}
    }

    F (i, 1, m2) {
        -- pos;
        AE (pos, t, 1, -b[i]);
        rk[++ len] = pos;
        F (j, el[i], er[i]) 
            if (mp[j]) {AE (j, pos, 1, 0);}
    }

    F (i, 1, _n) rk[++ len] = qwq[i];

    F (i, 1, _n - 1) {
        AE (qwq[i], qwq[i + 1], 1, qwq[i] - qwq[i + 1]);
    }

    SSP :: EK ();
    if (SSP :: ans != n) {
        cout << -1 << '\n'; return 0;
    } else {
        cout << - SSP::cst << '\n'; return 0;
    }
}

文章操作

相关推荐

评论

SOl p8461