喵喵题。
考虑若所有点权都已确定,如何求 \(1\) 到 \(n\) 所有路径权值和的 \(\gcd\)。
考虑如何 check 一个 \(x\) 是否合法。\(x\) 合法的充要条件是,把不能从 \(1\) 到达的点和不能到达 \(n\) 的点扔掉后,存在一组 \(\{f_n\}\),使得对于每条 \(u \to v\),边权为 \(d\) 的边,都满足 \(f_v - f_u \equiv d \pmod x\),且 \(f_1 = f_n = 0\)。\(f_i\) 的实际意义是,\(1 \to i\) 的所有路径的权值和模 \(x\) 的值。
但是这题不是边权而是点权。考虑拆点,在新图上连边 \(u \to u'\),边权 \(a_u\);\(u' \to u\),边权 \(-a_u\);原图 \(u \to v\) 的边在新图上连边 \(u' \longleftrightarrow v\),边权 \(0\)。那么判是否存在一组 \(\{f_n\}\) 等价于新图的所有环权值和模 \(x\) 意义下都是 \(0\)。
新图若忽略边权实际上是一张无向图。所以跑出新图的一棵 dfs 树,设根到 \(i\) 的路径边权和为 \(g_i\)。若设一条非树边为 \(u \to v\),边权为 \(d\),那么需要满足 \(g_u - g_v + d \equiv 0 \pmod x\)。所以 \(x\) 是所有这样的 \(|g_u - g_v + d|\) 的因数。那么把所有 \(|g_u - g_v + d|\) 取 \(\gcd\) 就是答案。
还有个问题是点权可能不确定。点权不确定的点就不连 \(u\) 和 \(u'\) 之间的边。这样新图可能不连通,跑出一个 dfs 森林即可。
code
// Problem: E - GCD of Path Weights
// Contest: AtCoder - AtCoder Regular Contest 144
// URL: https://atcoder.jp/contests/arc144/tasks/arc144_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 600100;
ll n, m, a[maxn], ans, f[maxn], dep[maxn];
vector<int> G[maxn], rG[maxn];
vector<pii> T[maxn];
pii E[maxn];
bool vis1[maxn], vis2[maxn], vis[maxn];
void dfs1(int u) {
vis1[u] = 1;
for (int v : G[u]) {
if (!vis1[v]) {
dfs1(v);
}
}
}
void dfs2(int u) {
vis2[u] = 1;
for (int v : rG[u]) {
if (!vis2[v]) {
dfs2(v);
}
}
}
void dfs(int u) {
vis[u] = 1;
for (pii p : T[u]) {
ll v = p.fst, d = p.scd;
if (!vis[v]) {
f[v] = f[u] + d;
dep[v] = dep[u] + 1;
dfs(v);
} else if (dep[v] < dep[u]) {
ans = __gcd(ans, abs(f[u] - f[v] + d));
}
}
}
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1, u, v; i <= m; ++i) {
scanf("%d%d", &u, &v);
G[u].pb(v);
rG[v].pb(u);
E[i] = mkp(u, v);
}
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
dfs1(1);
dfs2(n);
for (int i = 1; i <= n; ++i) {
if (a[i] != -1 && vis1[i] && vis2[i]) {
T[i].pb(i + n, a[i]);
T[i + n].pb(i, -a[i]);
}
}
for (int i = 1; i <= m; ++i) {
int u = E[i].fst, v = E[i].scd;
if (vis1[u] && vis2[u] && vis1[v] && vis2[v]) {
T[u + n].pb(v, 0);
T[v].pb(u + n, 0);
}
}
T[1].pb(n + n, 0);
T[n + n].pb(1, 0);
for (int i = 1; i <= n * 2; ++i) {
int j = (i > n ? i - n : i);
if (!vis[i] && vis1[j] && vis2[j]) {
dfs(i);
}
}
printf("%lld\n", ans == 0 ? -1LL : ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Regular Contest Weights Pathatcoder regular contest weights atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 167 atcoder regular contest 164 atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest builder disconnected atcoder regular contest