[DAG，DP]P6381

每条边有边权 $l$ 和值 $e$，求满足 e i e i + 1 = a k e_ie_{i+1}=a^k ei​ei+1​=ak 的连续边的边权和最大值。 n ≤ 1 0 5 , m ≤ 2 × 1 0 5 , w ≤ 1 0 5 , k ≤ 10 n\leq 10^5,m\leq 2\times10^5,w\leq10^5,k\leq 10 n≤105,m≤2×105,w≤105,k≤10。

一道很有意思的题，用到了很多方面的知识，很综合。

1.数学

这一题主要集中在对于 a b = c k ab=c^k ab=ck 这一处理。在不做任何处理前对于一个给定的 $a$ 是找不到唯一 $b$ 值的，这对做题很不方便。那么可以想到让 $a,b$ 对应起来。可以想到的方法就是分解质因数

a = p 1 a 1 p 2 a 2 . . . p n a n a=p_1^{a_1}p_2^{a_2}...p_n^{a_n} a=p1a1​​p2a2​​...pnan​​

那么对于每一个 a i a_i ai​ 而言，这道题只关心 a i M O D k a_i\,\,MOD\,\,k ai​MODk 的余数，而不是数本身。继续考虑，对于得到的 a i ′ a_i' ai′​ 而言，它的对应值就确定了，即

a ′ = p 1 a 1 ′ p 2 a 2 ′ . . . p n a n ′ a'=p_1^{a_1'}p_2^{a_2'}...p_n^{a_n'} a′=p1a1′​​p2a2′​​...pnan′​​
b = p 1 k − a 1 ′ p 2 k − a 2 ′ . . . p n k − a n ′ b=p_1^{k-a_1'}p_2^{k-a_2'}...p_n^{k-a_n'} b=p1k−a1′​​p2k−a2′​​...pnk−an′​​

a ′ , b a',b a′,b 相对应（这里需要特判 $k=1$ 的情况， $k=1$ 时 $a=b=1$）,所以在处理边时可以同时处理出一组 $a$ 到 $b$ 的映射（这里用数组 $g$ 代替）。同时考虑到在 $k$ 特别大时 $b$ 也会特别大，但是题目中的 w i ≤ 1 0 5 w_i\leq 10^5 wi​≤105 ，所以可以提前删掉不可行的部分（即不建边）。

特别注意，不建边并不意味着这条边不计入答案，在图连一条边也可能被计入答案，需要考虑到这一点。

给出建边部分代码，其中 $rt$ 和解释部分的 a ′ a' 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 f_{i,j} fi,j​ 表示点 $i$ 在上一条边的值为 $j$ 时走的边权最大，但直接开 1 0 5 × 2 × 1 0 5 10^5\times 2\times10^5 105×2×105 必定MLE。这里采取一种奇妙的方法。

用 map代替常规的数组，其余照常。具体来说，遍历到一个点时枚举所有的出边 $v$ ，先让 f [ v ] [ a ′ ] = l f[v][a']=l f[v][a′]=l ，即让这条边的初始长度等于边长，然后查找入边 $u$ ，如果找到了 f [ u ] [ g [ a ′ ] ] f[u][g[a']] f[u][g[a′]] （ g [ a ′ ] g[a'] g[a′] 是和自己的边对应的边）让 f [ v ] [ a ′ ] = m a x ( f [ v ] [ a ′ ] , f [ u ] [ g [ a ′ ] ] + l ) f[v][a']=max(f[v][a'],f[u][g[a']]+l) 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
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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！