Algoogle

Algorithm for Programming Contest

Codeforces 459E Pashmak and Graph

Category: Codeforces Tag: dp

Pashmak and Graph

問題概要


有向グラフ上で, 辺の重みが単調増加になるような最長のパスの長さを求めよ

解法


重さの小さい有向辺から見ていく.
pw[v] := vが最後使われた有向辺の重さ
dp[v][0] := 頂点vまで重さpw[v]を使って作る題意のパスの最長の長さ
dp[v][1] := 頂点vまで重さpw[v]未満の辺を使って作る題意のパスの最長の長さ
とすると
有向辺(u->v)で
dp[v][0] = max(dp[v][0], dp[u][1]+1)
となる(同じ重さの辺は使えないため)
また, dp[v][1]はvがpw[v]より重い辺で参照されたらすぐ更新する(当然pw[v]も).

これで最後にdp[v][i]の最大を求めれば良い.

コード


(459E.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;

struct edge
{
        int w, u, v;;
        edge(){}
        edge(int w, int u, int v):w(w),u(u),v(v){}
        bool operator<(const edge &e)const{ return w < e.w;}
};

int n, m, dp[300010][2], pw[300010];
vector<edge> E;

void update(int v, int w){
        if(pw[v] >= w) return;
        dp[v][1] = max(dp[v][1], dp[v][0]);
        dp[v][0] = 0;
        pw[v] = w;
}

int solve()
{
        sort(begin(E),end(E));
        for(auto &e: E) {
                update(e.u, e.w);
                update(e.v, e.w);
                dp[e.v][0] = max(dp[e.v][0], dp[e.u][1]+1);
        }
        int ret = 0;
        for (int i = 0; i < n; i++)
                ret = max(ret, max(dp[i][0], dp[i][1]));

        return ret;
}

void input()
{
        scanf("%d%d", &n, &m);
        int u, v, w;
        for (int i = 0; i < m; i++) {
                scanf("%d%d%d", &u, &v, &w);
                E.push_back(edge(w,u-1,v-1));
        }
}

int main()
{
        input();
        printf("%d\n", solve());
        return 0;
}

Comments