2017 ACM-ICPC 亚洲区(乌鲁木齐赛区)网络赛 H. Skiing
2024-08-31 20:22:28
题意:在这个寒假中,鲍勃有计划在山区度假胜地滑雪。这个滑雪胜地有M个不同的滑雪道和N个不同的标志位于那些转弯处点。从第S标记到第T标志的第i路径具有长度L。每个路径必须遵循降低高度的原则,起点必须严格高于终点。 现在,你应该帮助鲍勃找到最长的滑雪道。
思路:因为说起点必须严格高于终点,所以是一个有向图,而且不可能存在环,可以看作是一个DAG模型, 求DAG上的最长路可以用dp来求,有些时候也可以看作AOE网,这样就可以用拓扑排序来求关键路径来解决了;
代码:
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; #define MP make_pair const int N = + ; const int INF = 0x3f3f3f3f; vector<pair<int, int> > edge[N]; class Topological{ private: int tot = , vis[N], n; queue<int> Q; public: int in[N], dist[N], topo[N]; void Init(int n){ this -> n = n; for(int i = ; i <= n; ++ i) vis[i] = , dist[i] = - INF; } bool Topo_Sort(){ //拓扑排序 for(int i = ; i <= n; ++ i){ if(in[i] == ){ Q.push( i ); vis[i] = true; dist[i] = ; topo[tot++] = i; } } while(!Q.empty()){ int u = Q.front(); Q.pop(); for(int i = edge[u].size() - ; i >= ; -- i){ int v = edge[u][i].first; -- in[v]; if(in[v] == && !vis[v]){ vis[v] = true; Q.push( v ); topo[tot++] = v; } } } return tot == n ? true : false; } int Get_Cpm(){ //求关键路径 for(int i = ; i < tot; ++ i){ int u = topo[i]; for(int j = edge[u].size() - ; j >= ; -- j){ int v = edge[u][j].first; int c = edge[u][j].second; if(dist[v] < dist[u] + c) dist[v] = dist[u] + c; } } int ans = ; for(int i = ; i <= n; i++) if(dist[i] > ans) ans = dist[i]; return ans; } }Topo; void Input_data(int &n, int &m){ int u, v, c; scanf("%d %d", &n, &m); Topo.Init( n ); for(int i = ; i <= m; ++ i){ scanf("%d %d %d", &u, &v, &c); edge[u].push_back(MP(v, c)); ++ Topo.in[v]; } } int main(){ int T, n, m; scanf("%d", &T); while(T --){ Input_data(n, m); Topo.Topo_Sort(); printf("%d\n", Topo.Get_Cpm()); for(int i = ; i <= n; ++ i) edge[i].clear(); } }
最新文章
- 1Z0-053 争议题目解析577
- Java 技能树
- HTTP POST 提交问题
- 强连通 HDU3072
- 如何知道某个网站的IP地址
- 【leetcode】Spiral Matrix II
- MySQL 获得当前日期时间 函数
- maven_Error building POM (may not be this project&#39;s POM)错误
- ping命令使用技巧(一次Ping多个地址)
- java 字符串大小比较
- 用css3过滤做遮罩效果
- 在ssm框架中前后台数据交互均使用json格式
- Centos7解决图形界面卡死问题
- Kubernetes集群部署史上最详细(二)Prometheus监控Kubernetes集群
- winform 打印时的默认单位
- 用phpstudy配置网站遇到的一些问题
- 拦截器、过滤器、@Aspect 区别
- gcahce事物不够,借助binlog追上
- PHP随机函数rand()、mt_rand()、srand()、mt_srand() 的区别
- C#.NET常见问题(FAQ)-如何使用DataGridView跟Excel数据交互
热门文章
- HNOI2010 平面图判定(planar)
- 论文阅读:Forwarding Metamorphosis: Fast Programmable Match-Action Processing in Hardware for SDN
- oracle11G 同时支持IPV4和IPV6配置
- 「SCOI2015」小凸玩矩阵
- [CSP-S模拟测试]:集合合并(记忆化搜索)
- 揭开HTTPS的神秘面纱
- Iris Classification on Keras
- AndroidStudio 插件 之 Findbugs 安装与简单使用教程
- Android 中布局的优化措施都有哪些?
- PRISM 4 - RegisterViewWithRegion &; Custom Export Attributes