web analytics

JZOJ.4826 小澳的葫芦 解题报告

Description
小澳最喜欢的歌曲就是《葫芦娃》。
一日表演唱歌,他尽了洪荒之力,唱响心中圣歌。
随之,小澳进入了葫芦世界。
葫芦世界有n个葫芦,标号为1~ n。n个葫芦由m条藤连接,每条藤连接了两个葫芦,这些藤构成了一张有向无环图。小澳爬过每条藤都会消耗一定的能量。
小澳站在1号葫芦上(你可以认为葫芦非常大,可以承受小澳的体重),他想沿着藤爬到n号葫芦上,其中每个葫芦只经过一次。
小澳找到一条路径,使得消耗的能量与经过的葫芦数的比值最小。
Input
输入文件名为calabash.in。
输入文件第一行两个正整数n,m,分别表示葫芦的个数和藤数。
接下来m行,每行三个正整数u,v,w,描述一条藤,表示这条藤由u连向v,小澳爬过这条藤需要消耗w点能量。
Output
输出文件名为calabash.out。
一行一个实数,表示答案(绝对误差不超过 10^-3)。
Sample Input
4 6
1 2 1
2 4 6
1 3 2
3 4 4
2 3 3
1 4 8
Sample Output
2.000
【输入输出样例说明】
有4种爬法:
1->4,消耗能量8,经过2个葫芦,比值为8/2=4。
1->2->4,消耗能量1+6=7,经过3个葫芦,比值为7/3≈2.33。
1->3->4,消耗能量2+4=6,经过3个葫芦,比值为6/3=2。
1->2->3->4,消耗能量1+3+4=8,经过4个葫芦,比值为8/4=2。
所以选第三种或第四种方案,答案为2。

分析:

这道题其实是最小比例生成树。但是呢。我不知道的正解写法。于是呢,所以。用了一种奇技淫巧。因为这里是有向无环图。这个我们在这里可以用最短路的想法。spfa是个好东西。由题目可以得知。这道题其实就是想让我们求1~n所有路径里,(一条路径里)每条路的平均值最小。所以我们这里其实就是要求出每条路的最短路。。其实就是每次用多少边走下来的最短路。可能有些边数也走不到。那么把所有的这个边求出来,最后算平均值就好。

所以我们设d[i][j]是第i个点从起点走了j条边到达的最短路。visit[i][j]与前面对应。就是这样。

Post a Comment

You must be logged in to post a comment.