车站分级问题"/>
java 车站分级问题
符合了NOIP命题的特点,知识点不难,思维量是有的。
step1:把题读进去,理解。得到 非停靠点的等级 < 停靠点的等级
step2:把上述不等关系转化为有向图。即由非停靠点向停靠点连一条边
step3:对于每个入度为零的点dfs找最长路。取其max
step4:输出max+1
code:
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 500010;
int n, m, answer = -1e9, a[1010], start[1010], rudu[1010];
bool flag[1010];
struct edge{
int next, to, len;
}e[maxn<<2];
int cnt, head[maxn];
int dis[1010];
bool vis[1010], used[1010][1010];
void add(int u, int v, int w)
{
e[++cnt].to = v; e[cnt].next = head[u]; head[u] = cnt; e[cnt].len = w;
}
int SPFA(int s)
{
int ans = -1e9;
queue q;
while(!q.empty()) q.pop();
for(int i = 1; i <= n; i++) dis[i] = -1e9;
memset(vis, 0, sizeof(vis));
dis[s] = 0, vis[s] = 1, q.push(s);
while(!q.empty())
{
int now = q.front(); q.pop();
vis[now] = 0;
for(int i = head[now]; i != -1; i = e[i].next)
{
if(dis[e[i].to] < dis[now] + e[i].len)
{
dis[e[i].to] = dis[now] + e[i].len;
if(!vis[e[i].to])
{
q.push(e[i].to);
vis[e[i].to] = 1;
}
}
}
}
for(int i = 1; i <= n; i++)
if(dis[i] != 1e9) ans = max(dis[i], ans);
return ans;
}
int main()
{
freopen("testdata.in","r",stdin);
memset(head, -1, sizeof(head));
scanf("%d%d",&n,&m);
for(int i = 1; i <= m; i++)
{
int k;
memset(flag, 0, sizeof(flag));
memset(a, 0, sizeof(a));
scanf("%d",&k);
for(int j = 1; j <= k; j++)
{
scanf("%d",&a[j]);
flag[a[j]] = 1;
}
for(int j = a[1]; j <= a[k]; j++)
{
if(flag[j] == 0)
{
for(int l = 1; l <= k; l++)
if(used[j][a[l]] == 0)
{
add(j, a[l], 1);
used[j][a[l]] = 1;
rudu[a[l]]++;
}
}
}
}//build graph
int tot = 0;
for(int i = 1; i <= n; i++)
if(rudu[i] == 0) start[++tot] = i;
for(int i = 1; i <= tot; i++)
answer = max(answer, SPFA(start[i]));
printf("%d",answer+1);
}
洛谷P1983车站分级题解
题目 这个题非常毒瘤,只要还是体现在其思维难度上,因为要停留的车站的等级一定要大于不停留的车站的等级,因此我们可以从不停留的车站向停留的车站进行连边,然后从入度为0的点即不停留的点全都入队,然后拓扑排 ...
Luogu P1983 车站分级
(一周没写过随笔了) 这道题有坑! 看到题目,发现这么明显(??)的要求顺序,还有什么想法,拓扑! 将每条路范围内等级大于等于它的点(不能重复(坑点1))和它连一条边,注意起点终点都要有(坑点2),然 ...
洛谷P1983 车站分级
P1983 车站分级 297通过 1.1K提交 题目提供者该用户不存在 标签图论贪心NOIp普及组2013 难度普及/提高- 提交该题 讨论 题解 记录 最新讨论 求帮忙指出问题! 我这么和(diao ...
洛谷P1983车站分级
洛谷\(P1983\)车站分级(拓扑排序) 目录 题目描述 题目分析 思路分析 代码实现 题目描述 题目在洛谷\(P1983\)上 题目: 一条单向的铁路线上,依次有编号为 \(1, 2, -, ...
洛谷 P1983 车站分级
题目链接 题目描述 一条单向的铁路线上,依次有编号为 1,2,…,n的 n个火车站.每个火车站都有一个级别,最低 ...
P1983 车站分级[拓扑]
题目描述 一条单向的铁路线上,依次有编号为 1, 2, -, n1,2,-,n的 nn个火车站.每个火车站都有一个级别,最低为 11 级.现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟 ...
【洛谷P1983 车站分级】
这题好像是个蓝题.(不过也确实差不多QwQ)用到了拓扑排序的知识 我们看这些这车站,沿途停过的车站一定比未停的车站的级别高 所以,未停靠的车站向已经停靠的车站连一条边,入度为0的车站级别就看做1 然后 ...
P1983车站分级
%%%rqy 传送 我们注意到题目中这段话: 既然大于等于x的站都要停,那么不停的站的级别是不是都小于x?(这里讨论在始发站和终点站以内的站(注意这里是个坑)) 我们可以找出每趟车没停的站,向所有停了 ...
P1983 车站分级
题目描述 一条单向的铁路线上,依次有编号为 1, 2, …, n 的 n 个火车站.每个火车站都有一个级别,最低为 1 级.现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车 ...
随机推荐
dblink嵌套场景下 查询出现:ORACLE ORA-00600错误的解决
前段时间在做oracle查询的时候遇到了一个非常奇怪的现象,现将现象和解决过程记录下来,以备查看: 环境描述:A数据库通过dblink访问B数据库的视图,B数据库的视图的数据是通过B的dblink连接 ...
netcat使用
一.端口监听(实时消息) 首先在A计算机上,它充当的是服务器角色,$ nc -l 3333 这时就创建了一个监听端口(listening socket(server)).- -l 它让 nc 监听一个 ...
6to5 – 让你即刻体验 ECMAScript 6 编程
ECMAScript 6 是下一代的 ECMAScript 标准.ECMAScript 6 的目标是让 JavaScript 可以用来编写复杂的应用程序.函数库和代码的自动生成器. ES6 是这门语言 ...
ASP.NET 客户端静态文件请求设置缓存(Client Cache)
通常在服务器端大家都已经做了很多缓存的工作,ASP.NET CACHE也好MemeryCache也好却总是忽略了客户端缓存. 因为大家都知道不管哪个client都会缓存已经访问过的站点,但是浏览器缓存 ...
wget命令解析
今天一学信息安全的同学让我编写一个软件,功能大致如下:输入网站首页,自动下载该网站所有网页并保存?拿到后感觉属于搜索引擎相关的,说实话我就感觉会用到递归,不过我不会写,百度也没找到资料, ...
C语言中不同类型的循环(Different types of loops in C)
C语言中有三种类型的循环:for,while,do-while. while循环先判断循环条件. while (condition) { //gets executed after condition ...
QT---实现小球游戏(零基础入门)
本文章基本全代码敲窗口小球游戏,最后会免费加上源代码,让读者有更清晰的了解 内容主要覆盖: 1> Qtimer计时器的开始和结束,以及显示系统时间等等... 2> 多个Qwidget布局和 ...
三栏布局,div左右盒子是定宽,中间是自适应
用弹性布局flex: 给父盒子加个display:flex; 给中间盒子设flex=1; /* 弹性盒子布局*/ .wrap{ width: 100%; height: 90px; display: ...
SQLServer 常见高CPU利用率原因
1.缺失索引: USE AdventureWorks2014 SET STATISTICS TIME ON; SET STATISTICS IO ON ; SELECT per.FirstName,p ...
更多推荐
java 车站分级问题
发布评论