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。 这样可以通过所有测试点。
#include "cstdio"
#include "iostream"
#include "vector"
#include "queue"
#include "cstring" using namespace std ;
struct Edge { int to , next ;double val ,org; } ;//org原始的边权
const int maxN = ;
const double INF = 1e20 ;
const double eps = 1e- ;//误差范围 Edge e[ maxN << ] ;
double Dis[ maxN ] ;
bool vis[ maxN ] ;
int head[ maxN ] ; int cnt , N , M ; queue<int> q; int INPUT ( ) {
int x = , f = ; char ch = getchar ( ) ;
while ( ch < '' || ch > '' ) { if ( ch == '-')f = - ;ch = getchar ( ) ;}
while ( ch >='' && ch <='' ) { x = ( x << ) + ( x << ) + ch - '' ; ch = getchar ( ) ;}
return x * f ;
} void Add_Edge ( const int x , const int y , const double val ) {
e[ ++cnt ].to = y ;
e[ cnt ].org = val ;
e[ cnt ].next = head[ x ] ;
head[ x ] = cnt ;
} bool SPFA ( const double x ) {//纯SPFA算法
memset ( vis , false , sizeof ( vis ) ) ;
queue < int > Q ;
for ( int i= ; i<=N ; ++i )
Dis[ i ] = INF ;
for ( int i= ; i<=cnt ; ++i ) e[ i ].val = e[ i ].org - x ;
Q.push( ) ;
vis[ ] = true ;
Dis[ ] = ;
while ( !Q.empty( ) ) {
int t = Q.front ( ) ; Q.pop ( ) ; vis[ t ] = false ;
for ( int i=head[ t ] ; i ; i = e[ i ].next ) {
int temp = e[ i ].to ;
if ( Dis[ temp ] - eps > Dis[ t ] + e[ i ].val ) {
Dis[ temp ] = Dis[ t ] + e[ i ].val ;
if ( !vis[ temp ] ) {
Q.push( temp ) ;
vis[ temp ] = true ;
}
}
}
} return Dis[ N ] < -eps ;
} int main ( ) {
N = INPUT ( ), M = INPUT ( ) ;
for ( int i= ; i<=M ; ++i ) {
int _x = INPUT ( ) , _y = INPUT( ) , _val = INPUT ( ) ;
Add_Edge ( _x , _y , _val ) ;
}
Add_Edge ( , , ) ;//加入0虚拟节点
double l = , r = 1e3 ;
while ( r - l >= eps ) {//二分答案
double mid = ( l + r ) / 2.0 ;//2.0防止精度误差
if ( SPFA ( mid ) ) r = mid ;
else l = mid ;
}
printf ( "%.3lf" , l ) ;
return ;
}
calabash
NOIP_RP++;
2016-10-08 21:20:05
(完)