P1032 · OFFICIAL SOLUTION

P1032 金缕曲官方题解

Gioush OJ · P1032 金缕曲

金缕曲

【题意简述】

给定一张有向图和起点 $s$ 。经过一条初始权值为 $w$ 的边时，第 $j$ 次经过可获得 $w-\dfrac{j(j-1)}2$ 中仍为正的部分。可以重复经过边，求最大收益。

【Hint】

在同一个强连通分量内部，只要一条边能被经过，就可以通过绕行把它的正收益全部取完。不同强连通分量之间则只能沿 DAG 前进。

【提示】

先 Tarjan 缩点。分量内部边贡献全部加入分量权值，分量外边保留一次边权作为 DAG 转移贡献。

【解法】

对原图求强连通分量。对于一条边 $u\to v$ ：

若 $u,v$ 在同一强连通分量中，则这条边的全部正收益都可以取得，加入该分量的权值；
若不在同一分量中，则它成为缩点 DAG 上的一条边，经过时只能获得一次 $w$ 。

一条边的内部总收益可以直接求，也可以二分最大的 $t$ 使

\dfrac{t(t-1)}2<w.

缩点后在 DAG 上做最长路。设 $Dp_x$ 表示到达分量 $x$ 时最多已经取得的收益，则沿边 $x\to y$ 转移：

Dp_y\leftarrow \max(Dp_y,Dp_x+w+\operatorname{Sum}_y).

答案为所有可达分量的最大 $Dp$ 。

【分量内部边的贡献】

若一条边初始收益为 $w$ ，第 $j$ 次经过的正收益为 $w-\dfrac{j(j-1)}2$ 。在同一 SCC 内，进入后可以绕行并反复经过这条边，所以它的全部正收益都能取得。令最大的正收益次数为 $t$ ，满足 $\dfrac{t(t-1)}2<w$ ，将这 $t$ 项求和加入分量权值即可。

不同 SCC 之间不能绕回，缩点 DAG 上每条边至多使用一次，故只保留一次 $w$ 作为最长路转移。这样分量内“取尽”与分量间“至多一次”正好对应两类边。

【复杂度】

Tarjan 与 DAG 转移均为线性。若每条边的 $t$ 用二分求，复杂度为 $\mathcal{O}(n+m\log w)$ ；用公式求 $t$ 则为 $\mathcal{O}(n+m)$ 。

【参考代码】

1/*2Author:Ehundategh3Date:2026/7/234Name:goldknot.cpp5You steal,I kill.6*/7#include <cmath>8#include <stack>9#include <queue>10#include <cstdio>11#include <cstring>12#include <algorithm>13#define MAXN 100001014using namespace std;15 16int Head[2][MAXN],Total[2]={0,0},Dfn[MAXN],Low[MAXN],cnd=0,SCC[MAXN],cns=0,Deg[MAXN];17int n,m,In1,In2,In3,s,c,T;18long long Sum[MAXN],Dp[MAXN],Ans=0;19stack <int> S;20queue <int> Q;21 22struct edge {23    int St,Ed,Next,Val;24}Edge[2][MAXN<<1];25 26void Edge_Add(int St,int Ed,int Val,int Type) {27    Edge[Type][++Total[Type]]={St,Ed,Head[Type][St],Val};28    Head[Type][St]=Total[Type];29}30 31void Tarjan(int Now) {32    Dfn[Now]=Low[Now]=++cnd;33    S.push(Now);34    for (int i=Head[0][Now];i;i=Edge[0][i].Next) {35        int To=Edge[0][i].Ed;36        if (!Dfn[To]) {37            Tarjan(To);38            Low[Now]=min(Low[Now],Low[To]);39        }40        else if (!SCC[To]) {41            Low[Now]=min(Low[Now],Dfn[To]);42        }43    }44    if (Dfn[Now]==Low[Now]) {45        cns++;46        while (S.top()!=Now) {47            SCC[S.top()]=cns;S.pop();48        }49        SCC[S.top()]=cns;S.pop();50    }51}52 53long long Calc(int x) {54    int Bottom=floor(sqrt(2*x*1.0+0.25)-0.5);55    return 1ll*x*(Bottom+1)-1ll*(Bottom+1)*(Bottom+2)*Bottom/6;56}57 58void TopSort() {59    for (int i=1;i<=cns;i++) {60        Dp[i]=-(1ll<<60);61        if (Deg[i]==0) Q.push(i);62    }63    Dp[s]=Sum[s];64    while (Q.size()) {65        int Now=Q.front(); Q.pop();66        Ans=max(Ans,Dp[Now]);67        for (int i=Head[1][Now];i;i=Edge[1][i].Next) {68            int To=Edge[1][i].Ed;69            Dp[To]=max(Dp[To],Dp[Now]+Edge[1][i].Val+Sum[To]);70            Deg[To]--;71            if (Deg[To]==0) Q.push(To);72        }73    }74    return;75}76 77void Solve() {78    scanf("%d%d",&n,&m); Ans=0,Total[0]=Total[1]=0,cnd=0,cns=0;79    for (int i=1;i<=n;i++) Head[0][i]=Head[1][i]=0,Dfn[i]=Low[i]=0,SCC[i]=0,Deg[i]=0,Dp[i]=0,Sum[i]=0;80    for (int i=1;i<=m;i++) {81        scanf("%d%d%d",&In1,&In2,&In3);82        Edge_Add(In1,In2,In3,0);83    }84    scanf("%d",&s);85    for (int i=1;i<=n;i++) {86        if (!Dfn[i]) Tarjan(i);87    }s=SCC[s];88    for (int i=1;i<=m;i++) {89        int S1=SCC[Edge[0][i].St],S2=SCC[Edge[0][i].Ed],V=Edge[0][i].Val;90        if (S1==S2) {91            Sum[S1]+=Calc(V);92        }93        else {94            Edge_Add(S1,S2,V,1); Deg[S2]++;95        }96    }97    TopSort();98    printf("%lld\n",Ans);99}100 101int main() {102    freopen("goldknot.in","r",stdin);103    freopen("goldknot.out","w",stdout);104    scanf("%d%d",&c,&T);105    while (T-->0) Solve();106    return 0;107}