01分数规划 东师oj3582: 小澳的葫芦

题目描述
题目描述
小澳最喜欢的歌曲就是《葫芦娃》。
一日表演唱歌，他尽了洪荒之力，唱响心中圣歌。
随之，小澳进入了葫芦世界。
葫芦世界有n个葫芦，标号为1~ n。n个葫芦由m条藤连接，每条藤连接了两个葫芦，这些藤构成了一张有向无环图。小澳爬过每条藤都会消耗一定的能量。
小澳站在1号葫芦上（你可以认为葫芦非常大，可以承受小澳的体重），他想沿着藤爬到n号葫芦上，其中每个葫芦只经过一次。
小澳找到一条路径，使得消耗的能量与经过的葫芦数的比值最小。
输入
输入文件第一行两个正整数n,m，分别表示葫芦的个数和藤数。
接下来m行，每行三个正整数u,v,w，描述一条藤，表示这条藤由u连向v，小澳爬过这条藤需要消耗w点能量。
输出
一行一个实数，表示答案（误差不超过 10^-3）。
样例输入
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的路径。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 50005
#define inf 0x7fffffff
#define lim 1e-4 
using namespace std;
int n,m,s,tot,dcnt;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
  if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct EDGE{
    int to,nex;
    double v,x;
}ed[N*2];
int head[N*2];
inline void add(int x,int y,double  z){
    ++tot;
    ed[tot].nex=head[x];
    head[x]=tot;
    ed[tot].to=y;
    ed[tot].v=z;
}
double dis[N];
bool vis[N];
inline bool spfa(double k){
    for(int i=1;i<=tot;i++) ed[i].x=ed[i].v-k;
    for(int i=1;i<=n;i++) dis[i]=inf;
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(0);
    dis[0]=0;
    vis[0]=1;
    while(!q.empty()){
        int dmf=q.front();
        q.pop();
        vis[dmf]=0;
        for(int i=head[dmf];i;i=ed[i].nex){
            int hxr=ed[i].to;
            if(dis[hxr]>dis[dmf]+ed[i].x){
                dis[hxr]=dis[dmf]+ed[i].x;
                if(!vis[hxr]){
                    vis[hxr]=1;
                    q.push(hxr);
                }
            }
        }
    }
    return dis[n]<0;
}
int main(){
    n=read();
    m=read();
    for(int i=1;i<=m;++i){
        int u,v;
        double w;
        u=read();
        v=read();
        w=read();
        add(u,v,w);
    }
    add(0,1,0);
    double l=0;
    double r=1e3;
    while(r-l>=lim){
        double mid=(l+r)/2.0;
        if(spfa(mid)) r=mid;
        else l=mid;
    }
    printf("%.3lf",l);
    return 0;

}

再加上一个0点，那么这个问题就可以转化为求权值之和比边数之和最小

哈哈01分数规划