夏晓光(loveJY)的博客

洛谷四月月赛Div1T1

哇偶,看来我T1就不会做qwq

然后一个30暴力就把自己带走了

若正整数 $a$ 与 $b$ 满足：

$a$ 与 $b$ 的积是一个正整数的 $k$ 次方，即存在正整数 $c$ 使得 $ab=c^k$。

那么我们称 $(a,b)$ 为一组完美数对。

有一个包含 $n$ 个结点和 $m$ 条边的有向无环图，这张图中的每条边都有权值和长度两个属性。

如果一条路径 $P$ 满足以下条件之一，则称其为一条完美路径：

$P$ 中仅包含一条边。

$P$ 从其起点开始依次为 $e_1, e_2, e_3, \ldots e_p$​ 这 $p\ (p\ge 2)p$ 条边，对于任意的 $1\leq i\leq p-1$，$e_i$ 的权值和 $e_{i+1}$​ 的权值组成完美数对。

你需要求出图中最长完美路径的长度，一条路径的长度定义为这条路径上所有边的长度之和。

先不用说k=1或者n<=10了

k<=2?

我们发现有这样一个不难发现的规律,就是直接对于每个边的权值每个质因数因子%2,那么要求乘起来等于2?,然后你会发现如果要从一条边走向另一条边就一定这两条边权值相等

所以我们枚举每个权值,然后拿权值等于我们枚举的边去跑拓扑排序就好了

k<=10?

之前的结论其实还是有用的,进行之前那个取模之后,你会发现$a+b==k$,而且$a<k,b<k$,所以你会发现对于一个a只有一个唯一的b对吧

那么我们就可以和之前一样枚举一个权值,然后拿所有权值等于a和b的边去跑一个0/1状态的拓扑排序,这个很简单,因为毕竟只有两个状态

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
const int MAXN = 3e5 + 7;
struct rec {
	rec(int a = 0, int b = 0, int c = 0, int d = 0) {
		x = a, y = b, w = c, l = d;
	}
	int x, y, w, l;
};
int n, m, k, ans, ccnt, x, y, w, l, cnt;
int home[MAXN], to[MAXN], nxt[MAXN], in[MAXN];
int r[MAXN], vis[MAXN], dp[MAXN][2], f[MAXN];
queue<int> q;
vector<rec> v[MAXN];

bool cmp(rec a, rec b) {
	return r[a.x] < r[b.x];
}

void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
	in[y]++;
}

pair<int, int> proc (int a) {
	ll res1 = 1, res2 = 1;
	for(int i = 2; i * i <= a; ++i) {
		int tmp = 0;
		while(a % i == 0) {
			tmp++, a /= i;
		}
		if(tmp % k) {
			for(int j = 1; j <= tmp % k; ++j) {
				res1 = (res1 * i);
			}
			for(int j = 1; j <= k - tmp % k; ++j) {
				res2 = (res2 * i > 100000 ? 0 : res2 * i);
			}
		}
	}
	if(k != 1)res1 *= a;
	for(int j = 2; j <= k; ++j) {
		res2 = (res2 * a > 100000 ? 0 : res2 * a);
	}
	return make_pair((int)res1, (int)res2);
}

void topo() {
	for(int i = 1; i <= n; ++i) {
		if(!in[i]) {
			q.push(i);
			r[i] = ++cnt;
		}
	}
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int i = home[u]; i; i = nxt[i]) {
			if(--in[to[i]] == 0) {

				q.push(to[i]);
				r[to[i]] = ++cnt;
			}
		}
	}
	return;
}


int main() {
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d%d%d", &x, &y, &w, &l);
		pair<int, int> tmp = proc(w);
		if(tmp.second) {
			v[min(tmp.first, tmp.second)].push_back(rec(x, y, tmp.first, l));
			f[min(tmp.first, tmp.second)] = max(tmp.first, tmp.second);
		} else {
			ans = max(ans, l);
		}
		ct(x, y);
	}
	topo();
	for(int i = 1; i <= 100000; ++i) {
		int len = v[i].size();
		if(len == 0)continue;
		sort(v[i].begin(), v[i].end(), cmp);
		for(int j = 0; j < len; ++j) {
			if(vis[v[i][j].x] != i) {
				dp[v[i][j].x][0] = dp[v[i][j].x][1] = 0, vis[v[i][j].x] = i;
			}
			if(vis[v[i][j].y] != i) {
				dp[v[i][j].y][0] = dp[v[i][j].y][1] = 0, vis[v[i][j].y] = i;
			}
			if(v[i][j].w == i) {
				dp[v[i][j].y][0] = max(dp[v[i][j].y][0], dp[v[i][j].x][1] + v[i][j].l);
			}
			if(v[i][j].w == f[i]) {
				dp[v[i][j].y][1] = max(dp[v[i][j].y][1], dp[v[i][j].x][0] + v[i][j].l);
			}
			ans = max(ans, max(dp[v[i][j].y][0], dp[v[i][j].y][1]));
		}
	}
	printf("%d\n", ans);
	return 0;
}