首页 > 代码库 > CF261（D2）E DP

CF261（D2）E DP

2024-07-18 11:42:57   216人阅读

【题意】：

给出n，m，代表n个点、及m条有向边。然后m行给出每条有向边的u，v，w（权值）。

题目要求你求出最长路径的长度，是该路径满足权值严格递增。

数据范围 1 ≤ wi ≤ 10^5

【知识点】：

DP

【题解】：

一道看似图论的题目，其实可以利用递推的方法巧妙地解决。

因为权值的最大值为10^5，所以可以用权值表示下标，来保存边

然后遍历权值

tmp[v]表示在当前权值所在边为尾边的最大长度，用max(tmp[v], dp[u] + 1)更新

然后用tmp[v]更新dp[v]，dp[v]代表末端为v的最大长度

最后从1到n遍历dp 取最大值即为其答案

【代码】：

 1 #include <map> 2 #include <set> 3 #include <cmath> 4 #include <ctime> 5 #include <queue> 6 #include <stack> 7 #include <cstdio> 8 #include <string> 9 #include <vector>10 #include <cstring>11 #include <sstream>12 #include <iostream>13 #include <algorithm>14 #include <bitset>15 #include <climits>16 using namespace std;17 18 #define wh while19 #define inf (int)(~0u/2)20 #define FOR(i, n) for(int i = 0; i < n; i++)21 #define FOR1(i, n) for(int i = 1; i < n; i++)22 #define FOR2(i, n) for(int i = 0; i <= n; i++)23 #define REP(i,n) for(int i = 1; i <= n; i++)24 #define FORI(it,n) for(typeof(n.begin()) it = n.begin(); it != n.end(); it++)25 #define sf scanf26 #define pf printf27 #define frs first28 #define sec second29 #define psh push_back30 #define mkp make_pair31 #define PB(x) push_back(x)32 #define MP(x, y) make_pair(x, y)33 #define clr(abc,z) memset(abc,z,sizeof(abc))34 #define lt(v) v << 135 #define rt(v) v << 1 | 136 //#define mid ((l + r) >> 1)37 #define lson l, mid, v << 138 #define rson mid + 1, r, v << 1 | 139 40 #define fre freopen("1.txt", "r", stdin)41 42 typedef long long LL;43 typedef long double LD;44 45 const int maxn = 3e5 + 100;46 vector<pair<int, int> > w[maxn];47 int dp[maxn], tmp[maxn];48 49 int main(){50     int n, m;51     sf("%d%d", &n, &m);52     FOR(i, m){53         int u, v, len; sf("%d%d%d", &u, &v, &len);54         w[len].PB(MP(u, v));55     }56     FOR(i, maxn){57         int clen = w[i].size(), u, v;58         FOR(j, clen){59             v = w[i][j].second;60             tmp[v] = 0;61         }62         FOR(j, clen){63             u = w[i][j].first; v = w[i][j].second;64             tmp[v] = max(tmp[v], dp[u] + 1);65         }66         FOR(j, clen){67             u = w[i][j].first; v = w[i][j].second;68             dp[v] = max(dp[v], tmp[v]);69         }70     }71     int ans = 0;72     REP(i, n)73         ans = max(ans, dp[i]);74     pf("%d", ans);75 }

 


联系
我们