竞赛讨论区 > 求助两道图论题

求助两道图论题

头像
谔谔谔
发布于 2021-10-05 16:11:30 APP内打开
赞 1 | 收藏 0 | 回复1 | 浏览224

1.
条有向边连接了 个点, 每一条边上有一定数量的馅饼, 当计算鸭通过一条边的时候,他会收集这条边上所有的馅饼, 当计算鸭经过这条边收集完馅饼的时候, 这条边上会立刻重新出现一些馅饼, 第i次经过这条边后, 这条边上重新出现的馅饼的数量比上一次这条边上的馅饼数量少i. 具体说来, 比如一条边上一开始有x个馅饼, 那么计算鸭第一次经过这条边的时候可以收集到x个馅饼, 然后这条边重新出现了x-1个馅饼, 第二次经过这条边的时候可以收集到x-1个馅饼, 然后这条边重新出现了x-1-2个馅饼, 注意馅饼的数量不会小于0.

比如某一条边有9个馅饼, 那么前四次经过这条边可以收获的馅饼数量依次是9,8,6,3,从第五次开始就无法收获任何馅饼了.

现在问你从S点出发, 最多可以收获多少的馅饼

输入
第一行输入两个整数

接下来 行每行输入三个整数 表示从a点到b点有一条边有c个馅饼

最后一行输入一个整数 表示起点

输出

一个整数,即最多收获的馅饼

注: 可能会有自环或重边

30%的数据: 1 \le n \le 10, 1 \le m \le 101≤n≤10,1≤m≤10 , 所有边的初始馅饼数量小于等于5

60%的数据: 1 \le n \le 1000, 1 \le m \le 10001≤n≤1000,1≤m≤1000
100%的数据: 无限制

2.
个城市通过条道路互相连通, 一共有条旅游路线(路线是双向的), 条大巴,每辆大巴负责一条旅游路线, 现在有个询问, 每个询问问你最少需要换乘几次可以从城市到城市, 一条旅游路线上的一个城市可以到同一条旅游路线上另一个任意城市, 你的旅游只能通过这些特定路线的大巴来完成.

输入
第一行输入一个整数

接下来行每行输入两个整数 表示一条道路

接下来一行输入一个整数

接下来 行每行输入两个整数 表示一条旅游路线

接下来一行输入一个整数

接下来 行每行输入两个整数

输出
对于每个询问如果不能从 输出-1

否则输出最少需要换乘的大巴数量, 第一辆乘坐的大巴也算一次换乘

30%的数据:1≤n≤20,1≤m≤20,1≤q≤20
另外40%的数据: 树是一条链, 其他无限制

另外30%的数据: 无限制

求求了,说下思路

1条回帖

回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐