Luogu3980 [NOI2008] 志愿者招募

博主： tony102
发布时间：2021 年 02 月 27 日
1531 次浏览
暂无评论
2299字数
分类：题解

[Link](https://www.luogu.com.cn/problem/P3980)

## 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

```cpp
#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 日