ARC144E 题解

DaiRuiChen007 · 2024-05-07 16:42:11 · 题解

Problem Link

题目大意

给定 n 个点 m 条边的 DAG，点有点权，有一些点权不确定，找到一种方式最大化所有 1\to n 路径点权和的 \gcd。

数据范围：n\le 3\times 10^5。

思路分析

先删除所有不在 1\to n 路径上的点，然后拆点成边，使得答案变成路径边权和。

设答案为 p，根据经典结论，存在一组序列 d_1\sim d_n 使得 \forall (u,v)\in E,d_u+w(u,v)\equiv d_v\pmod p。

把图看成无向图，只要处理所有环的 \gcd 即可。

用可持久化并查集维护 d_{rt}-d_u 的值，遇到环时把答案和 d_u+w(u,v)-d_v 取 \gcd 即可。

时间复杂度 \mathcal O((n+m)\alpha(n))。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e5+5;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
bool vs[MAXN],vt[MAXN];
vector <int> G[MAXN];
int n,m,fa[MAXN<<1];
ll a[MAXN],d[MAXN<<1],ans=0;
void dfs(int u) {
    vs[u]=true;
    if(u==n) vt[u]=true;
    for(int v:G[u]) {
        if(!vs[v]) dfs(v);
        vt[u]|=vt[v];
    }
}
int find(int x) {
    if(x==fa[x]) return x;
    int c=find(fa[x]);
    d[x]+=d[fa[x]],fa[x]=c;
    return c;
}
signed main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=2*n;++i) fa[i]=i;
    for(int i=1,u,v;i<=m;++i) {
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
    }
    dfs(1);
    if(!vt[1]) return puts("-1"),0;
    for(int i=1;i<=n;++i) if(vt[i]) for(int j:G[i]) if(vt[j]) {
        fa[find(i+n)]=find(j);
    }
    for(int i=1;i<=n;++i) {
        scanf("%lld",&a[i]);
        if(vt[i]&&~a[i]) {
            if(find(i)!=find(i+n)) {
                int x=find(i);
                d[x]=a[i]-d[i],fa[x]=i+n;
            } else {
                ans=gcd(ans,abs(d[i+n]+a[i]-d[i]));
            }   
        }
    }
    if(find(1)==2*n) ans=gcd(ans,d[1]);
    printf("%lld\n",ans?ans:-1ll);
    return 0;
}