题目链接:Codeforces 459E Pashmak and Graph
题目大意:给定一张有向图,每条边有它的权值,要求选定一条路线,保证所经过的边权值严格递增,输出最长路径。
解题思路:将边按照权值排序,每次将相同权值的边同时加入,维护每个点作为终止点的最大长度即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 3 * 1e5+5;
struct edge {
int u, v, w;
}s[maxn];
bool cmp (const edge& a, const edge& b) {
return a.w < b.w;
}
int n, m, d[maxn], f[maxn], val[maxn];
int main () {
scanf("%d%d", &n, &m);
memset(d, 0, sizeof(d));
memset(f, 0, sizeof(f));
memset(val, 0, sizeof(val));
for (int i = 0; i < m; i++)
scanf("%d%d%d", &s[i].u, &s[i].v, &s[i].w);
sort(s, s + m, cmp);
for (int i = 0; i < m; i++) {
int j;
for (j = i; s[j].w == s[i].w && j < m; j++);
for (int k = i; k < j; k++)
d[s[k].v] = max(d[s[k].v], f[s[k].u] + 1);
for (int k = i; k < j; k++)
f[s[k].v] = d[s[k].v];
i = j - 1;
}
int ans = 0;
for (int i = 1; i <= n; i++)
ans = max(ans, f[i]);
printf("%d\n", ans);
return 0;
}
分享到:
相关推荐
Codeforces Round #620 (Div. 2) [codeforces 1304A] Two Rabbits 整除+模 总目录详见https://blog.csdn.net/mrcrack/article/details/103564004 在线测评地址https://codeforces.ml/contest/1304/problem/A ...
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
解决问题(문제해결) ACM-ICPC凭证,BOJ,CodeForces,Codewars,SCPC,摇动,TopCoder凭证
题目大意:给出一个数列 a ,求出 题目分析:如果暴力的话显然时间复杂度是 n * n 的,我们应该想办法去优化,比赛的时候想用线段树,但是不会在维护异或的前提下区间加法,也想过用矩阵维护,但丝毫没什么用呀,...
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
Codeforces - 1131C. Birthday(贪心)题目链接题目给你n和n个数,要你重新排列n个数,使得这些数的相邻差值中最大的那个值最小。stat
题目大意:给出 n 个数字组成的序列,现在可以对数列进行多次操作,每次操作可以选择其中一段连续的数列,用其平均数替换原位置,换句话说,若原连续数列为 1 2 3,则可以替换为 2 2 2,问如何操作可以使得最后答案...
题目分析:最优性问题,且是对区间操作的,而且数据范围满足 n^3 的时间复杂度,综上可以考虑区间dp,因为题目已经明确了需要求什么,所以我们不妨设 dp[ i ][ j ] 为区间 [ i , j ] 合并后的最短数列的长度,因为...
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
E. Array Shrinking time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given an array a1,a2,…,an. You can perform the following operation...
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
贪心正确性显然:R大的至少可以选则R做为点来用。所以按R升序遍历,每次优先选左边的,能让后边的可选的更多。 用set维护可选的数即可。 这题加了个输出2个方案。 我们考虑最简单的情况:即确定一个序列后,是否有2...
codeforces每日一练。 题意: 给一棵树,每个点有一个点权,每条边有一个边权,求一条链使得点权和-边权和最大。 思路: 由于我没看清楚题意,以为是求联通子图的点权和-边权和最大,用link-cut-tree写换根,wa10了两...
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 185A - Plant 全测试点49个
Codeforces global round 10 codes
# sublime-plugin-for-codeforces 自定义构建,用于从 codeforces 获取测试用例并检查程序是否正确。 平台:GNU/Linux 语言:Python2.7.9 描述:这个程序从 codeforces 中获取测试用例,并告诉你程序的输出是否与...