# 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，且路线不一定要为简单路径）

## Sample Input

``````3 3
1 2 1
2 3 2
3 1 3
``````

## Sample Output

``````3
``````

## 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
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() {
for (register int i = 0; i < m; ++i) {
// 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;
}
``````