题解 [ARC144E] GCD of Path Weights

· · 题解

下文中设原图为 G_1，拆点后的新图为 G_2。

设答案非 -1 时为 x，则我们只需要将所有权值为 -1 的点置为 x 即可，我们将在接下来的讨论中忽略它们所拆的边。

考虑将 G_1 中的点 u 拆成双向边 (u, u', a_u)，原来的边 u \to v 拆成双向边 (u', v, 0)。现在我们需要讨论 G_2 中的边权。

考虑先在 G_1 中去掉所有 1 不能到达或不能到达 n 的点，在 G_2 中也去掉这些点及其拆出的点。

对于 G_2 中任意一条 1 \to u \to v \to n' 的路径，如果我们将权值为 w 的 u \to v 换成另一条权值为 w' 的路径，则 x \mid |w - w'|。

对于剩下的点，我们考虑抓出 G_2 中的连通块，对每个连通块跑出任意一棵生成树，则对于该连通块内任意一条不全是树边的路径，我们都可以通过若干次把非树边替换成树上路径的操作将其变为一条全是树边的路径。

设 T(u, v) 表示树上 u, v 间边权和，则一条非树边 (u, v, w) 替换为树上路径所带来的边权和减少量为 T(u, v) - w，于是 x \mid |T(u, v) - w|。

由于非树边一共只有 O(m) 条，我们直接统计即可。

最后还有一个小问题：G_2 中可能本来存在 1 \to n' 的路径，而我们在上述操作中并没有统计到。实现时可以直接加边 (1, n', 0)。

综上，时间复杂度为 O((n + m) \log w)，其中 w 为值域 3 \times 10^{17}。

代码：

#include <stdio.h>
#include <stdlib.h>

typedef long long ll;

typedef struct {
    int nxt;
    int end;
    ll dis;
} Edge;

int cnt1 = 0, cnt2 = 0, cnt3 = 0;
int head1[300007], head2[300007], head3[600007];
ll val[600007];
bool vis1[300007], vis2[300007], vis3[600007];
Edge edge1[300007], edge2[300007], edge3[1200007];

inline void add_edge1(int start, int end){
    cnt1++;
    edge1[cnt1].nxt = head1[start];
    head1[start] = cnt1;
    edge1[cnt1].end = end;
}

inline void add_edge2(int start, int end){
    cnt2++;
    edge2[cnt2].nxt = head2[start];
    head2[start] = cnt2;
    edge2[cnt2].end = end;
}

inline void add_edge3(int start, int end, ll dis){
    cnt3++;
    edge3[cnt3].nxt = head3[start];
    head3[start] = cnt3;
    edge3[cnt3].end = end;
    edge3[cnt3].dis = dis;
}

void dfs1(int u){
    vis1[u] = true;
    for (int i = head1[u]; i != 0; i = edge1[i].nxt){
        int x = edge1[i].end;
        if (!vis1[x]) dfs1(x);
    }
}

void dfs2(int u){
    vis2[u] = true;
    for (int i = head2[u]; i != 0; i = edge2[i].nxt){
        int x = edge2[i].end;
        if (!vis2[x]) dfs2(x);
    }
}

ll gcd(ll a, ll b){
    return b == 0 ? a : gcd(b, a % b);
}

ll dfs3(int u, int n){
    ll ans = 0;
    vis3[u] = true;
    for (int i = head3[u]; i != 0; i = edge3[i].nxt){
        int x = edge3[i].end, x_ = x <= n ? x : x - n;
        if (vis1[x_] && vis2[x_]){
            if (!vis3[x]){
                val[x] = val[u] + edge3[i].dis;
                ans = gcd(ans, dfs3(x, n));
            } else {
                ans = gcd(ans, llabs(val[x] - val[u] - edge3[i].dis));
            }
        }
    }
    return ans;
}

int main(){
    int n, m;
    ll ans = 0;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++){
        int a, b, a_;
        scanf("%d %d", &a, &b);
        a_ = a + n;
        add_edge1(a, b);
        add_edge2(b, a);
        add_edge3(a_, b, 0);
        add_edge3(b, a_, 0);
    }
    for (int i = 1; i <= n; i++){
        ll a;
        scanf("%lld", &a);
        if (a != -1){
            int i_ = i + n;
            add_edge3(i, i_, a);
            add_edge3(i_, i, -a);
        }
    }
    add_edge3(1, n * 2, 0);
    dfs1(1);
    dfs2(n);
    for (int i = 1; i <= n; i++){
        if (vis1[i] && vis2[i]){
            int i_ = i + n;
            if (!vis3[i]) ans = gcd(ans, dfs3(i, n));
            if (!vis3[i_]) ans = gcd(ans, dfs3(i_, n));
        }
    }
    if (ans == 0){
        printf("-1");
    } else {
        printf("%lld", ans);
    }
    return 0;
}