[CF 459E] Pashmak and Graph

459E – Pashmak and Graph

思路

设$f_{i}$表示到$i$的最长路

将边按权值存下来,为了边权相同的值存下来,在以同一边权的边更新的时候要用一个新数组存下来更新

代码

#include <iostream>
#include <cstdio>
#include <vector>

struct Data{
	int x, y;
}a;

int n, m, f[300010];

std::vector<Data>vec[100010];

int main(){
	int z;
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; i++){
		scanf("%d%d%d", &a.x, &a.y, &z);
		vec[z].push_back(a);
	}
	for(int i=1; i<=100000; i++){
		int tmp[300010];
		for(int j=0; j<vec[i].size(); j++)
			tmp[vec[i][j].y]=f[vec[i][j].y];
		for(int j=0; j<vec[i].size(); j++)
			tmp[vec[i][j].y]=std::max(tmp[vec[i][j].y], f[vec[i][j].x]+1);
		for(int j=0; j<vec[i].size(); j++)
			f[vec[i][j].y]=tmp[vec[i][j].y];		
	}
	int ans=0;
	for(int i=1; i<=n; i++) ans=std::max(ans, f[i]);
	printf("%d", ans);
	return 0;
}
标签:

发表评论

电子邮件地址不会被公开。 必填项已用*标注