[HNOI2009]最小圈
2024-10-09 23:57:50
题目描述
对于一张有向图,要你求图中最小圈的平均值最小是多少,即若一个圈经过k个节点,那么一个圈的平均值为圈上k条边权的和除以k,现要求其中的最小值
输入输出格式
输入格式:
第一行2个正整数,分别为n和m
以下m行,每行3个数,表示边连接的信息,
输出格式:
一行一个数,表示最小圈的值,保留8位小数。
输入输出样例
输入样例#1:
4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3
输出样例#1:
3.66666667
说明
若设边权为v,那么n≤3000,m≤10000,v≤50000
%%%%SAC巨佬
使用二分求解。对于一个猜测的$mid$,只需判断是否存在平均值小于$mid$的回路。
如何判断?
假设存在一个包含$k$条边的回路,回路上各边权值为$w_1$ ,$w_2$ ,$...$,$w_k$ ,那么平均值小于$midv意味着:
$$w_1 +w_2 +...+w_k <k×mid$$
即:
$$(w_1 -mid)+(w_2 -mid)+...+(w_k -mid)<0$$
换句话说,只要把边$(a,b)$的权$w(a,b)$改成$w(a,b)-mid$,再判断新图中是否有负环即可。
存在负环,那么之前的不等式满足,即存在着更小的平均值,$r=mid$;不存在,$l=mid$。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct Node
{
int next,to;
double dis;
}edge[];
const double eps=1e-;
int num,head[],n,m;
double dist[];
bool vis[],flag;
void add(int u,int v,double d)
{
num++;
edge[num].next=head[u];
head[u]=num;
edge[num].to=v;
edge[num].dis=d;
}
void dfs(int x,double zyys)
{int i;
vis[x]=;
for (i=head[x];i;i=edge[i].next)
{
int v=edge[i].to;
if (dist[v]>dist[x]+edge[i].dis-zyys)
{
dist[v]=dist[x]+edge[i].dis-zyys;
if (vis[v])
{
flag=;
return;
}
dfs(v,zyys);
}
}
vis[x]=;
}
int main()
{int i,u,v;
double d;
cin>>n>>m;
for (i=;i<=m;i++)
{
scanf("%d%d%lf",&u,&v,&d);
add(u,v,d);
}
double l=,r=50000.0;
while (r-l>=eps)
{
double mid=(l+r)/2.0;
flag=;
memset(vis,,sizeof(vis));
memset(dist,,sizeof(dist));
for (i=;i<=n;i++)
if (vis[i]==)
dfs(i,mid);
if (flag) r=mid;
else l=mid;
}
printf("%.8lf\n",(l+r)/2.0);
}
最新文章
- chrome中获取元素的样式
- mysql基本语法
- Ubuntu 14 如何打开 .chm格式文档?
- spring mvc form表单提交乱码
- Android 核心组件 Activity 之上
- Linux上ld和ld.so命令的区别
- Custom.pm
- #include <;boost/thread.hpp>;
- 开源项目:底部动作条(BottomSheet)
- ansible role 执行顺序
- 【iOS】7.4 定位服务->;2.1.2 定位 - 官方框架CoreLocation: CLLocationManager(位置管理器)
- 读Zepto源码之操作DOM
- 【Alpha】——First scrum Meeting
- 深入理解计算机系统(4.2)------逻辑设计和硬件控制语言HCL
- django(权限、认证)系统—— Permissions和Group
- SQL Server进阶 索引
- [Chrome插件] SelectJd(京东自营筛选器) v1.0.0 发布
- shell脚本 切换用户
- windows下安装redis以及测试 --转载自http://www.cnblogs.com/lpyan/p/5608333.html
- c# .net WebRequest 始终报域名无法解析