题解-luogu-p3275糖果

题目链接

给定一个长度为$n$的序列以及$k$个条件，每个条件要求序列当中一个点的权值大于/小于/不大于/不小于/等于另一个点。求这个序列总和的最小值

$1 \le k,n \le 100000$

感谢@oy 的贡献

差分约束系统的模板题。

记 $d$ 数组为以 $S$ 为源点到各个节点的最长路。根据最长路的性质，如果存在一条边 $(u,v,w)$ ，则一定满足以下不等式：

$$
d[u]+w(u,v)\le d[v]
$$

我们可以将题目中给出的不等关系转化为图中的有向边，然后通过单源最长路求出的一组 $\lbrace d_n\rbrace$ 即为差分约束系统的一组解。

因此，在图中连一条边 $(u,v,w)$ 相当于对 $d[u]$ 和 $d[v]$ 的取值作出限制，我们只需在构造出一张有向图，并求出其单源最长路即为答案。

有向边的构造方式如下：

限制 $d[A]=d[B]$

$$
d[A]=d[B] \Leftrightarrow (d[B]\le d[A])\wedge(d[A]\le d[B])
$$
$$
\Leftrightarrow (d[B]+0\le d[A])\wedge(d[A]+0\le d[B])
$$

连边：$(A,B,0)$，$(B,A,0)$

限制 $d[A]<d[B]$
$$
d[A]<d[B]\Leftrightarrow d[A]+1\le d[B]
$$

连边：$(A,B,1)$

限制 $d[A]\geq d[B]$
$$
d[A]\ge d[B]\Leftrightarrow d[B]+0\le d[A]
$$

连边：$(B,A,0)$

限制 $d[A]>d[B]$
$$
d[A]>d[B]\Leftrightarrow d[B]+1\le d[A]
$$

连边：$(B,A,1)$

限制 $d[A]\le d[B]$

连边：$(A,B,0)$

限制 $d[i]>0$

连边：$(S,i,1)$

连完所有的边后，跑一遍单源最长路；如果存在正环则输出无解。

统计答案时记得开$long$ $long$。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define die {puts("-1"); exit(0);}
typedef long long ll;
const int MAXN = 100005;
struct Edge {
	int v, w;
	Edge(int v, int w) {
		this -> v = v, this -> w = w;
	}
};
vector<Edge> G[MAXN];
int N, K;
bool inq[MAXN];
int d[MAXN], cnt[MAXN];
inline void AddEdge(int u, int v, int w) {
	G[u].push_back(Edge(v, w));
}
void SPFA() {
	queue<int> q;
	q.push(N + 1);
	d[N + 1] = 0;
	inq[N + 1] = 1;
	while (q.size()) {
		int u = q.front();
		q.pop();
		if (cnt[u] >= N) die
		cnt[u]++;
		inq[u] = 0;
		for (vector<Edge>::iterator it = G[u].begin(); it != G[u].end(); it++) {
			int v = it -> v, w = it -> w;
			if (d[u] + w > d[v]) {
				d[v] = d[u] + w;
				if (inq[v] == 0) {
					inq[v] = 1;
					q.push(v);
				}
			}
		}
	}
}
int main() {
	scanf("%d%d", &N, &K);
	for (register int i = 1; i <= K; ++i) {
		int X, A, B;
		scanf("%d%d%d", &X, &A, &B);
		switch (X) {
			case 1:
				AddEdge(A, B, 0);
				AddEdge(B, A, 0);
				break;
			case 2:
				if (A == B) die
				AddEdge(A, B, 1);
				break;
			case 3:
				AddEdge(B, A, 0);
				break;
			case 4:
				if (A == B) die
				AddEdge(B, A, 1);
				break;
			case 5:
				AddEdge(A, B, 0);
				break;
		}
	}
	for (register int i = 1; i <= N; ++i)
		AddEdge(N + 1, i, 1);
	SPFA();
	ll ans = 0;
	for (register int i = 1; i <= N; ++i)
		ans += d[i];
	printf("%lld", ans);
	return 0;
}

# 差分约束系统, 最短路

题解-luogu-p3275糖果

Comments

一言（ヒトコト）

Recent

Categories

Tag Cloud

Your browser is out-of-date!