【XXI Open Cup GP of Korea F】 Interval Graph

Description

给定 \(n\) 个闭区间，第 \(i\) 个为 \([s_i, e_i]\)，权值为 \(w_i\)。定义这 \(n\) 个区间组成的“区间图”为，\(i, j\) 之间存在一条无向边当且仅当 \([s_i, e_i]\cap[s_j,e_j]\ne \varnothing\)。现在要求移除其中若干个区间，使剩下区间构成的区间图为森林。求保留区间权值和的最大值。

Hint

• \(1\le n\le 2.5\times 10^5\)
• \(1\le s_i \le e_i \le 5\times 10^5\)
• \(w_i\in [1, 10^{12}]\)

Solution

首先考虑一些区间的区间图是森林意味着区间之间有什么特征：森林说明没有环，而一个区间图不存在环的充要条件是：不存在一个位置 \(p\)，使得存在三个互不相同的 \(i, j, k\) 满足：\(p\in [s_i, e_i]\cap [s_j, e_j]\cap [s_k, e_k]\)。也就是说不能有一个位置上面覆盖三个及以上个区间。

那么我们考虑一个网络流模型：

• 一开始我们有 \(2\) 的流量：一个位置最多可以同时存在两个区间。
• 对于每个区间 \([s_i, e_i]\)，我们要走就会把他走完，那么连边 \(s_i \to (e_i + 1)\)，容量为 \(1\)，表示在 \([s_i, e_i]\) 的位置这个区间我们可能会消耗一个流量。费用显然为 \(w_i\)。
• 对于每个位置 \(p\)，连边 \(p\to (p+1)\)，容量为 \(2\)，表示兼容该位置选零到二个区间三种情况。

然后发现要保留尽量大的，于是将费用取相反数，就可以跑费用流了。

然后 SPFA 貌似死了，考虑使用 Dijkstra，但很显然有负权，而传统解决方案中的势能需要 SPFA。

但是我们发现这个图是个 DAG！所以 dp 一下就行了。

还有更简单的方法：设第 \(i\) 个位置的势能为 \(-10^{12}\times i\) 即可。但是这个我写炸了

Code

妙不可读的 shit code：

/*
 * Author : _Wallace_
 * Source : https://www.cnblogs.com/-Wallace-/
 * Problem : XXI Open Cup GP of Korea F. Interval Graph
 */
#include <algorithm>
#include <cstdio>
#include <queue>

const int N = 2e6 + 5;
typedef long long LL;

int n, s = 1, t = 500002;
LL ans = 0;
struct Edge {
	int to, cap, nxt; LL cost;
} E[N];
int head[N], etot = 1;
 
namespace DAG_MCMF {
	inline void add_arc(int u, int v, int cap, LL cost) {
		E[++etot] = Edge{v, cap, head[u], cost}, head[u] = etot;
		E[++etot] = Edge{u, 0, head[v], -cost}, head[v] = etot;
	}
	
	int pre[N], flow[N];
	LL dist[N], h[N];
	bool vis[N];
	
	void getH() {
		h[s] = 0;
		for (int i = s; i < t; i++)
			for (int j = head[i]; j; j = E[j].nxt)
				if (E[j].cap && h[E[j].to] > h[i] + E[j].cost)
					h[E[j].to] = h[i] + E[j].cost;
	}
	
	bool dijkstra() {
		for (int i = s; i <= t; i++)
			pre[i] = flow[i] = 0, dist[i] = 1e18, vis[i] = false;
		std::priority_queue<std::pair<LL, int> > pq;
		pq.emplace(dist[s] = 0, s), flow[s] = 2;
		while (!pq.empty()) {
			int x = pq.top().second; pq.pop();
			if (vis[x]) continue; vis[x] = 1;
			for (int i = head[x]; i; i = E[i].nxt) {
				int y = E[i].to; LL w = E[i].cost + h[x] - h[y];
				if (E[i].cap && dist[y] > dist[x] + w) {
					dist[y] = dist[x] + w, pq.emplace(-dist[y], y);
					pre[y] = i, flow[y] = std::min(flow[x], E[i].cap);
				}
			}
		}
		return dist[t] != 1e18;
	}
	void solve() {
		getH();
		while (dijkstra()) {
			for (int x = t; x ^ s; x = E[pre[x] ^ 1].to)
				E[pre[x]].cap -= flow[t], E[pre[x] ^ 1].cap += flow[t];
			ans += (dist[t] + h[t] - h[s]) * flow[t];
		}
	}
}

signed main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int l, r; LL w;
		scanf("%d%d%lld", &l, &r, &w), ++l, ++r;
		DAG_MCMF::add_arc(l, r + 1, 1, -w);
	}
	for (int i = s; i < t; i++)
		DAG_MCMF::add_arc(i, i + 1, 2, 0);
	DAG_MCMF::solve();
	printf("%lld\n", -ans);
	return 0;
}

【XXI Open Cup GP of Korea F】 Interval Graph

原文：https://www.cnblogs.com/-Wallace-/p/14401059.html