Description
给定 \(n\) 个点，\(m\) 条边的有向图，图中的任意一条有向边满足 边起点的编号小于边终点的编号。每个点有点权，但其中有些点的点权未知。
你需要找到一种给未知点权值的方案，使得 所有 \(1\to n\) 的路径点权和的最大公因数最大，或者告知答案可以无限大。输出这个最大值。
\(n,m\le 3\times 10^5\)，保证存在一条从 \(1\) 到 \(n\) 的通路
Solution
Code
const int N=1e6+10;
int n,m,dis[N];
vector<int> dir[N],rev[N];
vector<pair<int,int> >G[N];
bool vdir[N],vrev[N],vis[N];
signed main(){
n=read(); m=read();
for(int i=1;i<=m;++i){
int u=read(),v=read();
dir[u].emplace_back(v);
rev[v].emplace_back(u);
G[u+n].emplace_back(v,0);
G[v].emplace_back(u+n,0);
}
for(int i=1;i<=n;++i){
int v=read();
if(v==-1) continue;
G[i].emplace_back(i+n,v);
G[i+n].emplace_back(i,-v);
}
G[1].emplace_back(2*n,0);
auto dir_dfs=[&](auto &&self,int x)->void{
if(vdir[x]) return ;
vdir[x]=1;
for(auto t:dir[x]) self(self,t);
return ;
};
auto rev_dfs=[&](auto &&self,int x)->void{
if(vrev[x]) return ;
vrev[x]=1;
for(auto t:rev[x]) self(self,t);
return ;
};
dir_dfs(dir_dfs,1);
rev_dfs(rev_dfs,n);
int ans=0;
auto dfs=[&](auto &&self,int x)->void{
if(vis[x]) return ;
vis[x]=1;
for(auto [t,w]:G[x]){
int vv=t<=n?t:t-n;
if(!(vdir[vv]&&vrev[vv])) continue;
if(!vis[t]){
dis[t]=dis[x]+w;
self(self,t);
}else{
ans=gcd(ans,abs(dis[t]-dis[x]-w));
}
}
return ;
};
for(int i=1;i<=n;++i){
if(!(vdir[i]&&vrev[i])) continue;
if(!vis[i]) dfs(dfs,i);
if(!vis[i+n]) dfs(dfs,i+n);
}
if(!ans) puts("-1");
else print(ans);
return 0;
}