526互联

AtCoder Regular Contest 117 F Gateau

发布时间 2023-05-02 10:49:52作者: zltzlt

洛谷传送门

AtCoder 传送门

差分约束算法：给出 \(m\) 个不等式形如 \(x_{a_i} \le x_{b_i} + y_i\)，求是否有解。
考虑把不等式看成图上的三角不等式 \(dis_v \le dis_u + d\)，连边 \((b_i, a_i, y_i)\)，以 \(x_i\) 最大的位置跑最短路，如果图中有负环就无解。此时求出来的 \(dis_i\) 是 \(x_i \le 0\) 的最大解。

考虑二分答案 \(x\)，记 \(s\) 为前缀和数组，那么我们可以得到不等式：

  • \(s_0 = 0, s_{2n} = x\)，连边 \((0, 2n, x), (2n, 0, -x)\)；
  • \(s_i - s_{i-1} \ge 0\)，连边 \((i, i - 1, 0)\)；
  • \(i \in [0,n), s_{i+n} - s_i \ge a_i\)，连边 \((i + n, i, -a_i)\)；
  • \(i \in [0,n), x - (s_{i+n} - s_i) \ge a_{i+n}\)，连边 \((i, i + n, x - a_{i+n})\)。

直接跑 spfa 会 T。注意到删去 \(n\) 点后图长这样：

可以 dp 求出 \(2n\) 到 \(n-1, n+1, 0\) 的最短路，以及 \(n-1\) 到 \(0, n+1\) 的最短路。加上新点 \(n\) 后，只用计算与新加边有关的点，把整张图缩成 \(0, n-1, n, n+1, 2n\) 五个点，在新图上跑 spfa 即可。

总结：这种差分约束但是又不能直接跑 spfa 的题，考虑观察图的形态，用 dp 求出最短路，或者缩点。

code 
// Problem: F - Gateau
// Contest: AtCoder - AtCoder Regular Contest 117
// URL: https://atcoder.jp/contests/arc117/tasks/arc117_f
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 300100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;

ll n, a[maxn], m, f[maxn], head[maxn], len, g[maxn];
bool vis[maxn];

struct edge {
	ll to, dis, next;
} edges[99];

inline void add_edge(ll u, ll v, ll d) {
	edges[++len].to = v;
	edges[len].dis = d;
	edges[len].next = head[u];
	head[u] = len;
}

inline bool spfa() {
	queue<int> q;
	mems(f, 0x3f);
	mems(vis, 0);
	mems(g, 0);
	f[m] = 0;
	g[m] = 1;
	vis[m] = 1;
	q.push(m);
	while (q.size()) {
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for (int i = head[u]; i; i = edges[i].next) {
			ll v = edges[i].to, d = edges[i].dis;
			if (f[v] > f[u] + d) {
				f[v] = f[u] + d;
				if (!vis[v]) {
					vis[v] = 1;
					if ((++g[v]) >= 8) {
						return 0;
					}
					q.push(v);
				}
			}
		}
	}
	return 1;
}

inline bool check(ll x) {
	len = 0;
	mems(head, 0);
	mems(f, 0);
	f[m - 1] = f[m] = 0;
	f[n - 1] = -a[n - 1];
	for (int i = n - 2; i; --i) {
		f[i] = f[i + 1];
		f[i + n] = f[i + n + 1];
		ll p = f[i], q = f[i + n];
		f[i] = min(f[i], q - a[i]);
		f[i + n] = min(f[i + n], p + x - a[i + n]);
	}
	f[0] = f[1];
	add_edge(m, 0, f[0]);
	add_edge(m, n + 1, f[n + 1]);
	add_edge(m, n - 1, f[n - 1]);
	mems(f, 0);
	f[n - 1] = 0;
	f[m - 1] = x - a[m - 1];
	for (int i = n - 2; i; --i) {
		f[i] = f[i + 1];
		f[i + n] = f[i + n + 1];
		ll p = f[i], q = f[i + n];
		f[i] = min(f[i], q - a[i]);
		f[i + n] = min(f[i + n], p + x - a[i + n]);
	}
	f[0] = f[1];
	add_edge(n - 1, n + 1, f[n + 1]);
	add_edge(n - 1, 0, f[0]);
	add_edge(n, n - 1, 0);
	add_edge(n + 1, n, 0);
	add_edge(n, 0, -a[0]);
	add_edge(m, n, -a[n]);
	add_edge(0, m, x);
	add_edge(m, 0, -x);
	return spfa();
}

void solve() {
	scanf("%lld", &n);
	m = (n << 1);
	ll l = 0, r = 1e10, ans = -1;
	for (int i = 0; i < m; ++i) {
		scanf("%lld", &a[i]);
	}
	if (n == 1) {
		printf("%lld\n", a[0] + a[1]);
		return;
	}
	for (int i = 0; i < n; ++i) {
		l = max(l, a[i] + a[i + n]);
	}
	while (l <= r) {
		ll mid = (l + r) >> 1;
		if (check(mid)) {
			ans = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}