Link

Sol

不等式模型入门,这篇题解是适配不等式模型总结的,强烈建议先阅读部分这篇总结,否则可能不易理解或者理解有误。

从网上蒯的形式化题意:

给出一条直线上的$n$个点,$m$个区间$[l_i,r_i]$。选一些区间覆盖这条直线,使得每个点至少被覆盖$a_i$次,每个区间可以被用来覆盖多次,每覆盖一次的代价为$c_i$.求最小代价。

我们设$x_k$表示第$k个区间用来覆盖了多少次

那么对于直线上的每个点$i$,其被覆盖次数可以这么描述,并且满足如下的限制条件。

$$f_i = \sum_{i \in [l_k,r_k]} x_k \geq a_i$$

那么第二步,我们给$f_i$减去一个量$g_i \in [0,m - a_i]$, 使得该不等式变为等式

$$f_i - g_i = a_i$$

那么,我们来看一看什么情况下可以满足对于每一个元$x_k$,其在方程组中只出现在两个方程中并且系数一个为正一个为负。我们这里直接钦定系数的绝对值为$1$,也就是系数值可以是$+1,-1$ 。因为其实系数是多少都可以除掉变成$1$

首先可以通过差分,$f_0 = 0, f_{n+1} = n + 1$

$$f_i - g_i - f_{i-1} + g_{i-1} = \sum_{i \in [l_k, r_k]} x_k - \sum_{i-1 \in [l_k, r_k]} x_k - g_i + g_{i-1} = a_i - a_{i-1}$$

那么,有这么些差分得到的方程组,要满足上面那个条件。要使得$x_k$前面的系数为正,那么就是要让$l_k = i$ ,这样使其正好包含$i$却不包含$i-1$ 。同理,要使它前面的系数为负,只要$r_k = i - 1$ 即可使该区间正好不包含$i$却包含$i-1$

同时可以发现,等式的右边也就是$a_i - a_{i-1}$, 可以知道$\sum_{i} a_i - a{i-1}$ = 0

那么,现在我们已经通过代数变换完成了使方程组满足条件的步骤,接下来介绍建边的方法。

把每个方程看作一个点,把元看成边。那么系数为负的元作为出边流出一个方程组,系数为正的元入边流入作为方程组。能解出这样的元,当且仅当等式为$0$,也就是流量守恒(平衡。容量为变量的上下界,这里上下均无界只要设上界为$inf$即可。费用就是题目给你的费用。

对于常数项,我们可以通过源点和汇点来解决。设$d = a_i - a_{i-1}$ ,若$d > 0$ ,则从$s$向该方程连边。否则,该方程连一条边到汇点。容量均为$inf$,费用为$0$

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 2e5 + 5;
const int inf = 0x7f7f7f7f, s = 199922, t = 199938;

int n, m, num = 1, maxFlow, minCost;
int head[SIZE], cur[SIZE], dis[SIZE], vis[SIZE], a[SIZE];

struct node {
    int to, v, w, nxt;
} edge[SIZE << 1];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

void addEdge(int u, int v, int d, int w) {
    edge[++ num] = (node) {v, d, w, head[u]}, head[u] = num;
}

int spfa() {
    std::queue < int > q;
    memset(dis, inf, sizeof(dis));
    q.push(s), cur[s] = head[s], dis[s] = 0, vis[s] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop(), vis[u] = 0;
        for (int i = head[u], v; i; i = edge[i].nxt) {
            v = edge[i].to;
            if (edge[i].v > 0 && dis[v] > dis[u] + edge[i].w) {
                dis[v] = dis[u] + edge[i].w, cur[v] = head[v];
                if (!vis[v]) q.push(v), vis[v] = 1;
            }
        }
    }
    return dis[t] != dis[0];
}

int dinic(int u, int flow) {
    if (u == t) return flow;
    int ans = 0, k = 0; vis[u] = 1;
    for (int i = cur[u], v; i && flow; i = edge[cur[u]].nxt) {
        v = edge[i].to, cur[u] = i;
        if (edge[i].v > 0 && !vis[v] && dis[v] == dis[u] + edge[i].w) {
            k = dinic(v, std::min(edge[i].v, flow));
            if (!k) continue;
            ans += k, flow -= k, edge[i].v -= k, edge[i ^ 1].v += k, minCost += k * edge[i].w;
        }
    }
    vis[u] = 0; return ans;
}

signed main() {
    // freopen("code.in", "r", stdin);
    n = read(), m = read();
    for (int i = 1; i <= n; ++ i) a[i] = read();
    for (int i = 1, u, v, d; i <= m; ++ i) {
        u = read(), v = read(), d = read();
        addEdge(u, v + 1, inf, d); addEdge(v + 1, u, 0, -d);
    }
    for (int i = 1; i <= n + 1; ++ i) {
        int d = a[i] - a[i - 1];
        if (d >= 0) addEdge(s, i, d, 0), addEdge(i, s, 0, 0);
        else addEdge(i, t, -d, 0), addEdge(t, i, 0, 0);
    }
    for (int i = 1; i <= n; ++ i) addEdge(i + 1, i, inf, 0), addEdge(i, i + 1, 0, 0);
    while (spfa()) maxFlow += dinic(s, inf);
    printf("%lld\n", minCost);
    return 0;
}
最后修改:2021 年 08 月 20 日
如果觉得我的文章对你有用,请随意赞赏