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分数规划

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
2022-12-19 15:03
黑龙江大学_2024
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-20 00:05
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议