[HNOI2009]最小圈

题目描述

对于一张有向图，要你求图中最小圈的平均值最小是多少，即若一个圈经过k个节点，那么一个圈的平均值为圈上k条边权的和除以k，现要求其中的最小值

输入输出格式

输入格式：

第一行2个正整数，分别为n和m

以下m行，每行3个数，表示边连接的信息，

输出格式：

一行一个数，表示最小圈的值，保留8位小数。

输入输出样例

输入样例#1：

输出样例#1：

3.66666667

说明

若设边权为

使用二分求解。对于一个猜测的$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$。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 struct Node
 7 {
 8   int next,to;
 9   double dis;
10 }edge[200001];
11 const double eps=1e-9;
12 int num,head[100001],n,m;
13 double dist[100001];
14 bool vis[100001],flag;
15 void add(int u,int v,double d)
16 {
17   num++;
18   edge[num].next=head[u];
19   head[u]=num;
20   edge[num].to=v;
21   edge[num].dis=d;
22 }
23 void dfs(int x,double zyys)
24 {int i;
25   vis[x]=1;
26   for (i=head[x];i;i=edge[i].next)
27     {
28       int v=edge[i].to;
29       if (dist[v]>dist[x]+edge[i].dis-zyys)
30     {
31       dist[v]=dist[x]+edge[i].dis-zyys;
32       if (vis[v])
33         {
34           flag=1;
35           return;
36         }
37       dfs(v,zyys);
38     }
39     }
40   vis[x]=0;
41 }
42 int main()
43 {int i,u,v;
44   double d;
45   cin>>n>>m;
46   for (i=1;i<=m;i++)
47     {
48       scanf("%d%d%lf",&u,&v,&d);
49       add(u,v,d);
50     }
51   double l=0,r=50000.0;
52   while (r-l>=eps)
53     {
54       double mid=(l+r)/2.0;
55       flag=0;
56       memset(vis,0,sizeof(vis));
57       memset(dist,0,sizeof(dist));
58       for (i=1;i<=n;i++)
59     if (vis[i]==0)
60       dfs(i,mid);
61       if (flag) r=mid;
62       else l=mid;
63     }
64   printf("%.8lf
",(l+r)/2.0);
65 }