[CF459E] Pashmak and Graph

题目描述

Pashmak's homework is a problem about graphs. Although he always tries to do his homework completely, he can't solve this problem. As you know, he's really weak at graph theory; so try to help him in solving the problem.

You are given a weighted directed graph with

Help Pashmak, print the number of edges in the required path.

输入输出格式

输入格式：

The first line contains two integers $(2<=n<=3·10^{5}; 1<=m<=min(n·(n-1),3·10^{5})) $ . Then, m m m lines follows. The i i i -th line contains three space separated integers: ui u_{i} ui , vi v_{i} vi , wi w_{i} wi $ (1<=u_{i},v_{i}<=n; 1<=w_{i}<=10^{5}) $ which indicates that there's a directed edge with weight wi w_{i} wi from vertex ui u_{i} ui to vertex vi v_{i} vi .$

It's guaranteed that the graph doesn't contain self-loops and multiple edges.

输出格式：

Print a single integer — the answer to the problem.

输入输出样例

输入样例#1：

输出样例#1：

输入样例#2：

输出样例#2：

输入样例#3：

输出样例#3：

说明

In the first sample the maximum trail can be any of this trails: .

In the second sample the maximum trail is .

In the third sample the maximum trail is .

其实题目还是很水的。

在一条直线上的最长上升子序列我们都会，但是放在图上怎么办。

设$f[i][j]$为到点$i$，上一个经过的点是$j$的最长边数?显然不行，状态量爆炸，数组都开不下。

那既然在图上做不行，我们就把它转化到直线上。

我们必须让我们的转移时间接近线性，必须固定一维，枚举一维。

所以思考20分钟过后...
我们把边按照边权排序，这样往后递推的时候可以不用考虑边权的约束关系。

所以设$f[i]$为以点$i$为结尾的最长的边数。

然后枚举到一个边转移 : $f[v] = max left(f[v], f[u] + 1 ight)$。

但是会有边权相同的边，那我们就不能用前面相同的边权得到的结果更新这个点，所以另开一个数组$g$存储和这条边相同边权的更新之后的$f$数组，这样就保证了更新是合法的。

记得清空$g$数组，开栈维护更新过的点，可以吧时间复杂度降低到$O(N^2)$；

总是是水题。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define reg register
inline char gc() {
    static const int BS = 1 << 22;
    static unsigned char buf[BS], *st, *ed;
    if (st == ed) ed = buf + fread(st = buf, 1, BS, stdin);
    return st == ed ? EOF : *st++;
}
#define gc getchar
inline int read() {
    int res = 0;char ch=gc();bool fu=0;
    while(!isdigit(ch))fu|=(ch=='-'), ch=gc();
    while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=gc();
    return fu?-res:res;
}
#define N 300005
int n, m;
struct edge {
    int x, y, val;
    inline bool operator < (const edge & a) const {
        return val < a.val;
    }
}ed[N];
int f[N], g[N];
int stack[N], top;
int ans;

int main()
{
    n = read(), m = read();
    for (reg int i = 1 ; i <= m ; i ++)
        ed[i] = (edge){read(), read(), read()};
    sort(ed + 1, ed + 1 + m);
    for (reg int i = 1 ; i <= m ; i ++)
    {
        int j = i + 1;
        while(ed[i].val == ed[j].val) j ++;
        for (reg int k = i ; k < j ; k ++)
        {
            g[ed[k].y] = max(g[ed[k].y], f[ed[k].x] + 1);
            stack[++top] = ed[k].y;
        }
        while(top)
        {
            f[stack[top]] = max(f[stack[top]], g[stack[top]]);
            g[stack[top]] = 0;
            top--;
        }
        i = j - 1;
    }
    for (reg int i = 1 ; i <= n ; i ++) ans = max(ans, f[i]);
    cout << ans << endl;
    return 0;
}