acwing-361. 观光奶牛(0/1分数规划)「建议收藏」

acwing-361. 观光奶牛(0/1分数规划)「建议收藏」给定一张 L 个点、P 条边的有向图,每个点都有一个权值 f[i],每条边都有一个权值 t[i]。求图中的一个环,使“环上各点的权值之和”除以“环上各边的权值之和”最大。输出这个最大值。注意:数据保证至少存在一个环。输入格式第一行包含两个整数 L 和 P。接下来 L 行每行一个整数,表示 f[i]。再接下来 P 行,每行三个整数 a,b,t[i],表示点 a 和 b 之间存在一条边,边的权值为 t[i]。输出格式输出一个数表示结果,保留两位小数。数据范围2≤L≤1000,2≤P≤50

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给定一张 L 个点、P 条边的有向图,每个点都有一个权值 f[i],每条边都有一个权值 t[i]。

求图中的一个环,使“环上各点的权值之和”除以“环上各边的权值之和”最大。

输出这个最大值。

注意:数据保证至少存在一个环。

输入格式
第一行包含两个整数 L 和 P。

接下来 L 行每行一个整数,表示 f[i]。

再接下来 P 行,每行三个整数 a,b,t[i],表示点 a 和 b 之间存在一条边,边的权值为 t[i]。

输出格式
输出一个数表示结果,保留两位小数。

数据范围
2≤L≤1000,
2≤P≤5000,
1≤f[i],t[i]≤1000

输入样例:
5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2
输出样例:
6.00

题解
0/1规划

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 1e3 + 10;
const int M = 5e4 + 10;
const double eps = 1e-6;
int value[N];
struct Edge{ 
   
    int v,w,next;
}edge[M];
int head[N],c;
void add(int u,int v,int w){ 
   
    edge[c].v = v;
    edge[c].w = w;
    edge[c].next = head[u];
    head[u] = c ++;
}
int q[N],hh = 0,tt = 0;
int vis[N],cnt[N];
double dist[N];
bool check(double mid){ 
   
    memset(vis,0,sizeof vis);
    memset(cnt,0,sizeof cnt);
    tt = hh = 0;
    for(int i = 1;i <= n;i ++){ 
   
        q[tt ++] = i;
        vis[i] = true;
    }
    while(hh != tt){ 
   
        int t = q[hh ++];
        if(hh == N)hh = 0;
        vis[t] = false;
        for(int i = head[t];~i;i = edge[i].next){ 
   
            int v = edge[i].v;
            double w = value[t] - mid * edge[i].w;
            if(dist[v] < dist[t] + w){ 
   
                dist[v] = dist[t] + w;
            
                cnt[v] = cnt[t] + 1;
                if(cnt[v] >= n)return true;
                if(!vis[v]){ 
   
                    vis[v] = true;
                    q[tt ++] = v;
                    if(tt == N)tt = 0;
                }
            }
        }
    }
    return false;
}
int main(){ 
   
    cin>>n>>m;
    int x,y,w;
    memset(head,-1,sizeof head);
    for(int i = 1;i <= n;i ++)cin>>value[i];
    for(int i = 0;i < m;i ++){ 
   
        cin>>x>>y>>w;
        add(x,y,w);
    }
    double l = 0.0,r = 1010;
    while(r - l > 1e-4){ 
   
        double mid = (l + r) / 2;
        if(check(mid))l = mid;
        else r = mid;
    }
    printf("%.2lf\n",l);
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169113.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • javascript原生态ajax_ajax22

    javascript原生态ajax_ajax22(对低版本的ie不作兼容处理了,太过时,不知道谁还用) 本次演示采用原生javascript+php实现ajax的 post 和 get功能; 对php不了解的同学不用担心,就两三行代码,而且我会详细说明; 好了,下面开始: 第一步:如果想要运行起来,那么还是需要开启服务器的,这里推荐使用wampserver,        下载相应的

  • 蓝牙音频编码方式_aac蓝牙编码

    蓝牙音频编码方式_aac蓝牙编码https://zhuanlan.zhihu.com/p/265597723早在2000年,蓝牙耳机就已经出现,但由于技术限制,只能用于通话。2008年,随着蓝牙A2DP(AdvancedAudioDistributionProfile)开始普及,立体声蓝牙耳机日渐流行。发展到现在,手机的耳机插口几近取消,双无线(TWS,TrueWirelessStereo)耳机正处于爆发期…本文从蓝牙音频传输原理讲起,从旧到新介绍五种蓝牙音频编码,最后落脚实地,介绍如何选择和配置耳机/手机的蓝牙

  • jetson tx1 配置SSD固态硬盘「建议收藏」

    jetson tx1 配置SSD固态硬盘「建议收藏」转载自:http://blog.csdn.net/hit2015spring/article/details/62217289配置外置SSD这里用的是三星EVO250G的SSD,支持SATA接口,ssd插上去开机是不能用的,TX1是没有识别的,需要的格式化为Linux支持的文件系统ext4.一系列配置之后可以把ssd设置为外置的存储,然后再把文件系统拷贝到SSD

  • 香农编码和哈夫曼编码_香农编码效率可以大于1吗

    香农编码和哈夫曼编码_香农编码效率可以大于1吗香农编码哈夫曼编码费诺编码的比较文章目录哈夫曼编码编码步骤例子优点缺点费诺编码编码步骤例子优点缺点香农编码编码步骤例子优点缺点参考备注:本文除了例子与数据,其他内容均为整合网络资源。哈夫曼编码编码步骤S1将信源符号按照概率大小从大到小排列;S2把概率最小的两个信源符号分成一组,其中,上面一个编码为0,下面一个编码为1,并将这两个符号的概率加起来,其结果再与尚未处理过的符号重…

  • CSS半透明边框效果

    CSS半透明边框效果源代码:&lt;!doctypehtml&gt;&lt;html&gt;&lt;head&gt;&lt;metacharset="utf-8"&gt;&lt;style&gt;div{ width:500px; height:309px; border:50pxsolidhsla(0,0%,100%,0.5); background:url(file:///C:/Use…

  • JAVA简历1到三年

    JAVA简历1到三年JAVA开发工程师_3年基本资料求职意向意向职位: Java开发工程师 求职地址:北京期待薪资:面议到岗时间:随时工作性质:全职 目前状况:已离职个人技能1.熟练Java语言基础语法以及面向对象特征。2.熟练Java语言中常用API的使用,如IO,String,Collection等。3.熟练MySQL的增删改查操作以及JDBC数据库连接池的使用。4.熟悉Git这种分布式版本的控制系统的使用。5.熟悉Spring、Springmvc、M

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号