【Atcoder】AtCoder Regular Contest 144 E – GCD of Path Weights | 图论、结构

标题链接

E – GCD of Path Weights (atcoder.jp)

标题粗心

给定有 $n$ 个点 $m$ 条边的有向无环图，给定长度为 $n$ 的整数数组 a1,a2,…,ana_1,a_2,…,a_na1​,a2​,...,an​。若 ai(1≤i≤n)a_i(1\le i\le n)ai​(1≤i≤n) 为 $-1$，阐明图中第 $i$ 个节点的点权不知道，否则阐明该点的点权为 $i$。为点权不知道的节点赋值，最大化从节点 $1$ 到节点 $n$ 之间一切途径点权和的最大公约数。

若不存在最大的答案，输出 -1。

思路

容易发现图中 $1$ 无法抵达、或许无法抵达 $n$ 的节点对答案没有影响，可以直接删去。然后咱们进行一步转化，途径点权和让人无从下手，咱们先把每个节点拆成两个节点，则点权转变为边权。比方样例 $1$:

4 4
1 2
1 3
2 4
3 4
-1 3 7 -1

咱们转化后建出的图为：

假设从节点 $1$ 到节点 $n$ 之间一切途径边权和都是$x$的倍数，那么一定可以给每个点分配一个权值 p1,p2,,…,pnp_1,p_2,,…,p_np1​,p2​,,...,pn​，使得对每条有权值的有向边$(u,v,w)$，都满足pv≡pu+w(modx)p_v\equiv p_u+w\pmod xpv​≡pu​+w(modx)。由于咱们只关心有向边两端点权值的相对巨细，咱们可以用加权并查集进行保护：
记 $f[x]$ 表明 $x$ 在加权并查集中的父节点，$dt[x]$ 表明 px+dt[x]≡pf[x](modx)p_x+dt[x]\equiv p_{f[x]}\pmod xpx​+dt[x]≡pf[x]​(modx)。
途径紧缩如下图所示，直接令 $dt$ 相加即可：

所以用并查集保护两点之间的差有什么用处呢？下面咱们来阐明求解该问题的具体流程。

首要咱们先将原图中的边加入到加权并查集中，这些边的边权均为 $0$。

然后对于输入的旧图上第 $i$ 个点的点权 aia_iai​，也就是转化后点 $i.1$ 和 $i.2$ 之间的边权，先查询两种是否在同一个并查集中：

• 假如不在，需求进行合并。

• 假如在，阐明 $dt[i.1]\equiv dt[i.2]+a[i]\mathrm{m}\mathrm{o}\mathrm{d}x$，所以最终的答案是 $|dt[i.2]+a[i]-dt[i.1]|$ 的因数。

这样咱们就可以找到一切给定点权对答案进行的约束了，显然咱们自己乱填的点权不会给答案更多约束，所以对一切约束取最大公约数即可。留意假如从节点 $1$ 能直接经过确定边权的途径抵达节点 $n$，那么最终的答案还需求与任一从节点 $1$ 到节点 $n$ 的途径长度取最大公约数（见样例 $4$）。

代码

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <math.h>
#include <map>
#include <queue>
#include <vector>
#include <stdlib.h>
#include <time.h>
using namespace std;
using LL=long long;
const int N=1e6+5;
//const LL mod=998244353;
const LL mod=1e9+7;
int n,m,k,x[N],y[N];
LL a[N],dt[N];
int f[N],vis[N],vv[N];
vector<int> e[N];
int find(int x)
{
	if (f[x]==x) return x;
	find(f[x]);
	dt[x]=dt[x]+dt[f[x]];
	return f[x]=f[f[x]];
}
void dfs(int u)
{
	vv[u]=1;
	if (u==n) vis[u]=1;
	for (auto v:e[u])
	{
		if (!vv[v]) dfs(v);
		if (vis[v]) vis[u]=1;
	}
}
LL gcd(LL a,LL b)
{
	if (b) return gcd(b,a%b);
	return a;
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n*2;++i) f[i]=i;
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d",&x[i],&y[i]);
		e[x[i]].push_back(y[i]);
	}
	dfs(1);
	if (!vis[n]) return printf("-1\n"),0;
	for (int i=1;i<=m;++i)
		if (vis[x[i]]&&vis[y[i]]) f[find(x[i]*2)]=find(y[i]*2-1);
	LL ans=0;
	for (int i=1;i<=n;++i)
	{
		scanf("%lld",&a[i]);
		if (!vis[i]) continue;
		if (a[i]==-1) continue;
		if (find(i*2-1)!=find(i*2))
		{
			dt[f[i*2-1]]=a[i]-dt[i*2-1];
			f[f[i*2-1]]=i*2;
		}
		else ans=gcd(ans,abs(dt[i*2]+a[i]-dt[i*2-1]));
	}
	if (find(1)==(n*2)) ans=gcd(ans,dt[1]);
	if (ans==0) ans--;
	printf("%lld\n",ans);
	return 0;
}