每条边有边权 \(l\) 和值 \(e\)，求满足 \(e_ie_{i+1}=a^k\) 的连续边的边权和最大值。 \(n\leq 10^5,m\leq 2\times10^5,w\leq10^5,k\leq 10\)。
一道很有意思的题，用到了很多方面的知识，很综合。
1.数学
这一题主要集中在对于 \(ab=c^k\) 这一处理。在不做任何处理前对于一个给定的 \(a\) 是找不到唯一 \(b\) 值的，这对做题很不方便。那么可以想到让 \(a,b\) 对应起来。可以想到的方法就是分解质因数
\[a=p_1^{a_1}p_2^{a_2}...p_n^{a_n} \]那么对于每一个 \(a_i\) 而言，这道题只关心 \(a_i\,\,MOD\,\,k\) 的余数，而不是数本身。继续考虑，对于得到的 \(a_i'\) 而言，它的对应值就确定了，即
\[a'=p_1^{a_1'}p_2^{a_2'}...p_n^{a_n'} \]\[b=p_1^{k-a_1'}p_2^{k-a_2'}...p_n^{k-a_n'} \]\(a',b\) 相对应（这里需要特判 \(k=1\) 的情况， \(k=1\) 时 \(a=b=1\)）,所以在处理边时可以同时处理出一组 \(a\) 到 \(b\) 的映射（这里用数组 \(g\) 代替）。同时考虑到在 \(k\) 特别大时 \(b\) 也会特别大，但是题目中的 \(w_i\leq 10^5\) ，所以可以提前删掉不可行的部分（即不建边）。
特别注意，不建边并不意味着这条边不计入答案，在图连一条边也可能被计入答案，需要考虑到这一点。
给出建边部分代码，其中 \(rt\) 和解释部分的 \(a'\) 等同， \(rb\) 和 \(b\) 相同， \(inn\) 记录入边信息，方便跑DAG。
for(int i=1;i<=m;++i){
int u=in(),v=in(),w=in(),l=in();
int sq=sqrt(w)+1;
long long rt=1,rb=1;
for(int j=2;j<=sq;++j){
int cnt=0;
while(w%j==0){
w/=j;
cnt++;
}
cnt=cnt%k;
rt*=pow(j,cnt);
if(cnt!=0 && k!=1){
rb*=pow(j,k-cnt);
}
}
if(w!=1 && k!=1){
rt*=w;
rb*=pow(w,(k-1));
}
if(rb<=100000){
g[rt]=rb;
g[rb]=rt;
adde(u,v,rt,l);
inn[v]++;
}
ans=max(ans,l);
}
2.DAG上跑DP
首先想到用 \(f_{i,j}\) 表示点 \(i\) 在上一条边的值为 \(j\) 时走的边权最大，但直接开 \(10^5\times 2\times10^5\) 必定MLE。这里采取一种奇妙的方法。
用 map 代替常规的数组，其余照常。具体来说，遍历到一个点时枚举所有的出边 \(v\) ，先让 \(f[v][a']=l\) ，即让这条边的初始长度等于边长，然后查找入边 \(u\) ，如果找到了 \(f[u][g[a']]\) （ \(g[a']\) 是和自己的边对应的边）让 \(f[v][a']=max(f[v][a'],f[u][g[a']]+l)\) 即可。一边更新DP值一边更新 \(ans\) 最后即为答案。
Updata:本题可用 unordered_map 写，实测开O2后跑到了200多ms，巨快！
for(int i=1;i<=n;++i){
if(inn[i]==0)
q.push(i);
}
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
int w=e[i].w;
int l=e[i].c;
f[v][w]=max(f[v][w],l);
if(f[u].find(g[w])!=f[u].end()){
f[v][w]=max(f[v][w],f[u][g[w]]+l);
}
inn[v]--;
if(inn[v]==0){
q.push(v);
}
ans=max(ans,f[v][w]);
}
}
最后放上完整代码
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int head[100005],ecnt,dp[100005];
int dep[100005],inn[100005],ans;
int g[100005];
map<int,int> f[100005];
queue <int> q;
struct edge{
int to,nxt,w,c;
}e[200005];
void adde(int u,int v,int w,int c){
e[++ecnt].nxt=head[u];
e[ecnt].to=v;
e[ecnt].w=w;
e[ecnt].c=c;
head[u]=ecnt;
}
int in(){
int x=0,f=1;
char c;
do{
c=getchar();
if(c=='-')
f=-1;
}while(c<'0' || c>'9');
while(c>='0' && c<='9'){
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x*f;
}
int main(){
n=in(),m=in(),k=in();
for(int i=1;i<=m;++i){
int u=in(),v=in(),w=in(),l=in();
int sq=sqrt(w)+1;
long long rt=1,rb=1;
for(int j=2;j<=sq;++j){
int cnt=0;
while(w%j==0){
w/=j;
cnt++;
}
cnt=cnt%k;
rt*=pow(j,cnt);
if(cnt!=0 && k!=1){
rb*=pow(j,k-cnt);
}
}
if(w!=1 && k!=1){
rt*=w;
rb*=pow(w,(k-1));
}
if(rb<=100000){
g[rt]=rb;
g[rb]=rt;
adde(u,v,rt,l);
inn[v]++;
}
ans=max(ans,l);
}
for(int i=1;i<=n;++i){
if(inn[i]==0)
q.push(i);
}
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
int w=e[i].w;
int l=e[i].c;
f[v][w]=max(f[v][w],l);
if(f[u].find(g[w])!=f[u].end()){
f[v][w]=max(f[v][w],f[u][g[w]]+l);
}
inn[v]--;
if(inn[v]==0){
q.push(v);
}
ans=max(ans,f[v][w]);
}
}
printf("%d",ans);
return 0;
}