[문제 풀이] CF 894 E Ralph and Mushrooms (축 점)

[문제 풀이] CF 894 E Ralph and Mushrooms (축 점)
이거 보라색?방정식 을 푸 는 알고리즘 을 주다.
고 리 를 반복 해서 옮 겨 다 닐 수 있다 면 고리 가 있 고 고리 가 있 는 것 을 설명 할 수 있다 면 고리 에 있 는 버섯 을 잘 말 릴 것 입 니 다. 모든 것 에서 마른 것 까지 의 공헌 이 얼마나 되 는 지 를 고려 해 보 겠 습 니 다 \ \ [\ 섬 {i = 0} ^ x (w - \ \ \ 섬 {j = 0} \ \ 섬 {i = 0} ^ x (w - {i (i + 1) \ \ \ \ \ \ 2} \ \ \ \ \ (x \ \ \ \) 의 값 을 풀 고, 중학교 지식 에 따라 \ \ \ \ (x = \ \ \ \ \ \ \ \ \ \ \ lflor {- 1 + \ \ \ \ ssssqrt {1 + 8w + 8 w} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ rfloor \), 전처리 \ (\ sum{i (i + 1) \ \ over 2} \) 공헌 도 를 직접 계산 할 수 있 습 니 다 (사실 통항 공식 도 풀 수 있 습 니 다)
그리고 Tarjan 이 줄 여서 DAG 의 DP 가 되 고 권한 과 변 권 이 있 는 DAG DP 가 됩 니 다.
시간 복잡 도

//@winlere
#include
#include
#include
#include
#include
#include

using namespace std;  typedef long long ll;   char __buf[1<<18],*__c=__buf,*__ed=__buf;
inline int qr(){
    register int ret=0,f=0;
    register char c=getchar();
    while(!isdigit(c))f|=c==45,c=getchar();
    while(isdigit(c)) ret=ret*10+c-48,c=getchar();
    return f?-ret:ret;
}

const int maxn=1e6+5;
struct E{int to,w;};
vector e[maxn],e2[maxn];
inline void add(const int&fr,const int&to,const int&w){e[fr].push_back({to,w});}
inline void add2(const int&fr,const int&to,const int&w){
    e2[fr].push_back({to,w});
}
int n,m;
int qaq[maxn],cnt;
ll w[maxn],dp[maxn];
bool usd[maxn];
int low[maxn],dfn[maxn],in[maxn],stk[maxn],top,siz[maxn];
ll s[maxn];
 
void dfs(const int&now){
    stk[++top]=now; in[now]=1;
    low[now]=dfn[now]=++*dfn;
    for(auto t:e[now]){
        if(!dfn[t.to]) dfs(t.to),low[now]=min(low[now],low[t.to]);
        else if(in[t.to]) low[now]=min(dfn[t.to],low[now]);
    }
    if(low[now]==dfn[now]){
        ++cnt;
        int temp;
        do temp=stk[top--],in[temp]=0,qaq[temp]=cnt,++siz[cnt];
        while(temp!=now);
    }
}

ll Dp(const int&now){
    if(usd[now]) return dp[now];
    dp[now]=0;
    for(auto t:e2[now]) dp[now]=max(dp[now],Dp(t.to)+t.w);
    usd[now]=1;
    return dp[now]=w[now]+dp[now];
}

int main(){
    n=qr(); m=qr();
    for(int t=1,t1,t2,t3;t<=m;++t) t1=qr(),t2=qr(),t3=qr(),add(t1,t2,t3);
    for(int t=1;t>1);
    int S=qr();
    dfs(S);
    for(int t=1;t<=n;++t)
        for(auto i:e[t]){
            if(qaq[t]==qaq[i.to]) {
                int k=(sqrt((long double)1+8ll*i.w)-1)/2.0;
                w[qaq[t]]=w[qaq[t]]+(k+1ll)*i.w-s[k];
            }
            else add2(qaq[t],qaq[i.to],i.w);
        }
    ll ans=Dp(qaq[S]);
    printf("%lld
",ans);
    return 0;
}