CFR 459 E. Pashmak and Graph ( DP )

Problem - E - Codeforces

題意：
給一張帶權有向圖。求最長路徑長度，路徑滿足邊權嚴格遞增。

數據範圍：
節點 2 ≤ N ≤ 3e5
邊數 1 ≤ M ≤ min( N * ( N - 1 ) / 2, 3e5 )
邊權 1 ≤ W[ i ] ≤ 1e5
保證無自環，無重邊。

解法：
先考慮將邊權小至大排序。此時發現，若邊權皆相異，那麼由邊權小到大，對當前的邊的終點以起點的 dp值更新不會遺失答案。問題出在於，對於當前考慮的某個邊，若起點的 dp值是依賴著邊權和當前這個邊相同的另某個邊的時候，按定義是不可轉移的。因此，此時會希望可以用類似滾動的方式，一次轉移同一個邊權的邊。但事實上，需要乾淨的空間只有相同邊權的邊裡的終點們，所以整體更新的複雜度 O( M )。

int N, M;
vi U, V, W;

void init(){
    cin >> N >> M;
    U = V = W = vi( M );
    for( int i = 0; i < M; ++i )
        cin >> U[ i ] >> V[ i ] >> W[ i ];
}

vvp w_edge;
vi dp;

void preprocess(){
    w_edge = vvp( MAXW + 1 );
    for( int i = 0; i < M; ++i )
        w_edge[ W[ i ] ].emplace_back( U[ i ] - 1, V[ i ] - 1 );
    dp = vi( N );
    vi t( N );
    for( int i = 1; i <= MAXW; ++i ){
        for( int j = 0; j < w_edge[ i ].size(); ++j )
            t[ w_edge[ i ][ j ].second ] = 0;
        for( int j = 0; j < w_edge[ i ].size(); ++j )
            upmax( t[ w_edge[ i ][ j ].second ], dp[ w_edge[ i ][ j ].first ] + 1 );
        for( int j = 0; j < w_edge[ i ].size(); ++j )
            upmax( dp[ w_edge[ i ][ j ].second ], t[ w_edge[ i ][ j ].second ] );
    }
}

void solve(){
    cout << *max_element( dp.begin(), dp.end() ) << endl;
}