当前位置: 首页 > news >正文

分数规划

模板洛谷P4951

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=410,M=1e4+10;
const double eps=1e-6;
typedef long long LL;
struct edge{LL u,v,c,t;
}e[M];
LL n,m,f;
int fa[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);
}
bool check(double k){for(int i=1;i<=n;i++){fa[i]=i;}sort(e+1,e+m+1,[&](edge& x,edge& y){return x.t*k+x.c<y.t*k+y.c;});double sum=0;for(int i=1;i<=m;i++){int u=e[i].u,v=e[i].v;int t=e[i].t,c=e[i].c;int fu=find(u);int fv=find(v);if(fu==fv)continue;sum+=k*t+c;fa[fu]=fv;}return f-sum>=eps;
}int main(){// cin.tie(nullptr)->sync_with_stdio(false);cin>>n>>m>>f;for(int i=1;i<=m;i++){cin>>e[i].u>>e[i].v>>e[i].c>>e[i].t;}double l=0,r=f;while(r-l>eps){double mid=(l+r)/2;if(check(mid))l=mid;elser=mid;}printf("%.4lf\n",l);return 0;
}
http://www.hskmm.com/?act=detail&tid=25230

相关文章:

  • CSS - transition 粗浅记忆
  • 【MC】LittleTiles模组结构数据解析和版本迁移方案
  • 容器魔方导致盒子满了
  • 课程学习笔记——[大一秋]遗传学
  • P3067 [USACO12OPEN] Balanced Cow Subsets G
  • Vivado 2025 界面中文设置
  • 词汇学习——专业词汇
  • P4556 [Vani有约会] 雨天的尾巴 [模板] 线段树合并
  • P4550 收集邮票
  • P8110 [Cnoi2021] 矩阵
  • P9751 [CSP-J 2023] 旅游巴士
  • P9234 [蓝桥杯 2023 省 A] 买瓜
  • P1044 [NOIP 2003 普及组] 栈
  • P1080 [NOIP 2012 提高组] 国王游戏
  • 音响没声音
  • P1654 OSU!
  • DynamoDB十年演进:云原生数据库的技术革新
  • 完整教程:MySQL全量、增量备份与恢复
  • 10/5
  • 10/4
  • 嵌入式MCU
  • porting perf性能观测工具
  • Windows常用快捷指令
  • Python 在金融中的应用- Part 1 - 教程
  • QBXT2025S刷题 Day4
  • java学习日记9.25
  • porting 开源memtester
  • 计算机的组成
  • 完整教程:用mediamtx搭建简易rtmp,rtsp视频服务器
  • oppoR9m MTK 6755 开启VCOM的9008模式