3．小澳的葫芦
（calabash.cpp/c/pas）
【题目描述】
小澳最喜欢的歌曲就是《葫芦娃》。
一日表演唱歌，他尽了洪荒之力，唱响心中圣歌。
随之，小澳进入了葫芦世界。
葫芦世界有n个葫芦，标号为1~ n。n个葫芦由m条藤连接，每条藤连接了两个葫芦，这些藤构成了一张有向无环图。小澳爬过每条藤都会消耗一定的能量。
小澳站在1号葫芦上（你可以认为葫芦非常大，可以承受小澳的体重），他想沿着藤爬到n号葫芦上，其中每个葫芦只经过一次。
小澳找到一条路径，使得消耗的能量与经过的葫芦数的比值最小。
【输入格式】
输入文件名为calabash.in。
输入文件第一行两个正整数n,m，分别表示葫芦的个数和藤数。
接下来m行，每行三个正整数u,v,w，描述一条藤，表示这条藤由u连向v，小澳爬过这条藤需要消耗w点能量。
【输出格式】
输出文件名为calabash.out。
一行一个实数，表示答案（误差不超过 10^-3）。
【输入输出样例】
|
calabash.in |
calabash.out |
|
4 6 1 2 1 2 4 6 1 3 2 3 4 4 2 3 3 1 4 8 |
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。
【数据规模与约定】
|
测试点编号 |
n |
m |
特殊说明 |
|
1 |
2 |
1 |
|
|
2 |
100 |
99 |
除1外，所有葫芦的入度均为1 |
|
3 |
100 |
105 |
所有从1到n的路径经过的葫芦数相等 |
|
4 |
100 |
1000 |
|
|
5 |
100 |
1000 |
|
|
6 |
199 |
198 |
除1外，所有葫芦的入度均为1 |
|
7 |
200 |
231 |
所有从1到n的路径经过的葫芦数相等 |
|
8 |
200 |
2000 |
|
|
9 |
200 |
2000 |
|
|
10 |
200 |
2000 |
|
对于所有数据，小澳爬过每条藤消耗的能量不会超过10^3，且一定存在一条从1到n的路径。
—————————————————分割线———————————————
分析：
【algorithm1】 第一个测试点只有一条边，输出 w/2 就可以啦。 可以通过第 1 个测试点。
【algorithm2】 注意到“除 1 外，所有葫芦的入度均为 1”，也就是说，从 1 到 n 的路径只有 一条，输出这一条路径的长度与这条路径上的点数的比值就可以了。 可以通过第 1、2、6 个测试点。
【algorithm3】 对于这样一类特殊数据，“所有从 1 到 n 的路径经过的葫芦数相等”，也就 是说 1~n 的最短路就是最优路径，最短路的长度与路径上的点数的比值就是答 案。 可以通过第 1、2、3、6、7 个测试点。
【algorithm4】 另建一个起点 0，连接一条 0 到 1 长度为 0 的边，就此将问题转化为长度和 边数最小比值。这个问题的求解需要分数规划。 假设答案为 ans，对于任意一条由 k 条边组成的路径，有： ( w1 + w2 + w3 + …+wk ) / k >= ans ；
转化一下： ( w1 + w2 + w3 + … + wk ) >= ans * k ； 即 ( w1 - ans ) + ( w2 - ans ) + ( w3 - ans ) + … + ( wk - ans ) >= 0 。 于是就得到了这样一个算法： 二分答案 x，每次将每一条边的权值减去 x 求最短路，判断 1~n 的最短路是 否大于 0：若大于 0，则说明答案 ans>x；否则说明 ans<x。 这样可以通过所有测试点。
1 #include "cstdio" 2 #include "iostream" 3 #include "vector" 4 #include "queue" 5 #include "cstring" 6 7 using namespace std ; 8 struct Edge { int to , next ;double val ,org; } ;//org原始的边权 9 const int maxN = 10010 ; 10 const double INF = 1e20 ; 11 const double eps = 1e-4 ;//误差范围 12 13 Edge e[ maxN << 2 ] ; 14 double Dis[ maxN ] ; 15 bool vis[ maxN ] ; 16 int head[ maxN ] ; 17 18 int cnt , N , M ; 19 20 queue<int> q; 21 22 int INPUT ( ) { 23 int x = 0 , f = 1 ; char ch = getchar ( ) ; 24 while ( ch < '0' || ch > '9' ) { if ( ch == '-')f = - 1 ;ch = getchar ( ) ;} 25 while ( ch >='0' && ch <='9' ) { x = ( x << 1 ) + ( x << 3 ) + ch - '0' ; ch = getchar ( ) ;} 26 return x * f ; 27 } 28 29 void Add_Edge ( const int x , const int y , const double val ) { 30 e[ ++cnt ].to = y ; 31 e[ cnt ].org = val ; 32 e[ cnt ].next = head[ x ] ; 33 head[ x ] = cnt ; 34 } 35 36 bool SPFA ( const double x ) {//纯SPFA算法 37 memset ( vis , false , sizeof ( vis ) ) ; 38 queue < int > Q ; 39 for ( int i=1 ; i<=N ; ++i ) 40 Dis[ i ] = INF ; 41 for ( int i=1 ; i<=cnt ; ++i ) e[ i ].val = e[ i ].org - x ; 42 Q.push( 0 ) ; 43 vis[ 0 ] = true ; 44 Dis[ 0 ] = 0 ; 45 while ( !Q.empty( ) ) { 46 int t = Q.front ( ) ; Q.pop ( ) ; vis[ t ] = false ; 47 for ( int i=head[ t ] ; i ; i = e[ i ].next ) { 48 int temp = e[ i ].to ; 49 if ( Dis[ temp ] - eps > Dis[ t ] + e[ i ].val ) { 50 Dis[ temp ] = Dis[ t ] + e[ i ].val ; 51 if ( !vis[ temp ] ) { 52 Q.push( temp ) ; 53 vis[ temp ] = true ; 54 } 55 } 56 } 57 } 58 59 return Dis[ N ] < -eps ; 60 } 61 62 int main ( ) { 63 N = INPUT ( ), M = INPUT ( ) ; 64 for ( int i=1 ; i<=M ; ++i ) { 65 int _x = INPUT ( ) , _y = INPUT( ) , _val = INPUT ( ) ; 66 Add_Edge ( _x , _y , _val ) ; 67 } 68 Add_Edge ( 0 , 1 , 0 ) ;//加入0虚拟节点 69 double l = 0 , r = 1e3 ; 70 while ( r - l >= eps ) {//二分答案 71 double mid = ( l + r ) / 2.0 ;//2.0防止精度误差 72 if ( SPFA ( mid ) ) r = mid ; 73 else l = mid ; 74 } 75 printf ( "%.3lf" , l ) ; 76 return 0 ; 77 }
NOIP_RP++;
2016-10-08 21:20:05
(完)