Codeforces 459E(加边DP)

Codeforces 459E
题意：一个有向图，找出一条最长的路径，这条路径上的每条边权重都严格递增，问最长的长度是多少？

这题要求每条边权重都严格递增，那么直接把所有边权存起来按照大小排序，之后每种边权进行加边，就可以做 DP 了，因为排序保证了每条边权重都严格递增，只需要 DP 算出最优解即可。

本题求边权严格递增的路径，把边按照大小排序，把选择化为添加边，和CF 841D异曲同工。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;

const int MAXN = 300000 + 5;

int n, m, dp[MAXN], tmp[MAXN];
vector<pair<int, int > > ed[MAXN];

void clean() {
}
int solve() {
    clean();
    for (int u, v, w, i = 1; i <= m; i++) scanf("%d%d%d", &u, &v, &w), ed[w].push_back(make_pair(u, v)); 
    for (int i = 1; i <= 100000; i++) {
        if ((int)ed[i].size() == 0) continue;
        for (int j = 0; j < (int)ed[i].size(); j++) {
            int u = ed[i][j].first, v = ed[i][j].second;
            tmp[v] = 0;
        }
        for (int j = 0; j < (int)ed[i].size(); j++) {
            int u = ed[i][j].first, v = ed[i][j].second;
            tmp[v] = max(dp[u] + 1, tmp[v]);
        }
        for (int j = 0; j < (int)ed[i].size(); j++) {
            int u = ed[i][j].first, v = ed[i][j].second;
            dp[v] = max(dp[v], tmp[v]);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dp[i]);
    printf("%d\n", ans);
    return 0; 
}
int main() {
    scanf("%d%d", &n, &m), solve();
    return 0;
}