Skip to content

11408: 【原1408】Hentai’s Travel

题目

题目描述

author: Xue Zhendong 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1408

Description

Hentai喜欢旅行。这回他要在序号为1到n的n个城市之间旅行。这n个城市之间共有m条连接两个城市的单行公路。Hentai在公路上旅行时喜欢看风景,因此他给每条公路的风景评了一个分ai。他是一个先苦后甜的人(这道题中是这样),因此他在挑选旅行路线时经过某条路时看到的风景比上一条经过的公路的风景分数更高。Hentai想看到尽可能多的风景,请你告诉他他能找到的最长的满足他要求旅行路线有多长。(每条公路长度视为1,且路线不一定要为简单路径)

Input Format

第一行为两个整数数n,m(2 ≤ n ≤ 300000; 1 ≤ m ≤ min(n·(n - 1), 300000))。 接下来m行,每行三个整数xi,yi,ai(1 ≤ ai ≤ 100000)分别代表每条公路的起点序号、终点序号、风景分数。 数据保证没有自环或重边。

Output Format

输出共1行,为满足要求的最长的路线的长度。

Sample Input

3 3
1 2 1
2 3 2
3 1 3

Sample Output

3

Hint

对于30%的数据,n ≤ 10, m ≤ 50, ai ≤ 100;

对于60%的数据,n ≤ 1000, m ≤ 5000, ai ≤ 1000;

对于100%的数据,n, m≤300000, 1 ≤ ai ≤ 100000;

yyong119's solution

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define MAX_N 300005
using namespace std;
struct Node {
    int from, to, weight;
}e[MAX_N];
int n, m, ans;
int f[MAX_N];
vector<int> out_edge[MAX_N];// id of edges that from node x
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res * flag;
}
inline bool cmp(const Node &p, const Node &q) {
    return p.weight > q.weight;
}
int dfs(int x) {
    if (f[x]) return f[x];
    int ans = 0, to = e[x].to;
    for (register int i = 0; i < out_edge[to].size(); ++i) 
        if (e[out_edge[to][i]].weight > e[x].weight)
            ans = max(ans, dfs(out_edge[to][i]));
        else break;
    return ans + 1;
}
int main() {
    n = read(), m = read();
    for (register int i = 0; i < m; ++i) {
        int x = read(), y = read(), w = read();
        // out_edge[x].push_back(i);
        e[i].from = x; e[i].to = y; e[i].weight = w;
    }
    sort(e, e + m, cmp);
    for (register int i = 0; i < m; ++i)
        out_edge[e[i].from].push_back(i);
    f[0] = 1; ans = 1;
    for (register int i = 1; i < m; ++i) {
        if (!f[i]) f[i] = dfs(i);
        ans = max(ans, f[i]);
    }
    printf("%d", ans);
    return 0;
}