题目大意：
给定一张带点权和边权的无向图
G
G
G
,求出一张图
G
′
∈
G
G’\in G
G
′
∈
G
,使得下面这个式子：
∑
w
(
V
i
)
∑
δ
(
u
i
,
v
i
)
;
V
i
,
u
i
,
v
i
∈
G
′
.
\frac{\sum w(V_i)}{\sum{\delta(u_i,v_i)}};V_i,u_i,v_i\in G’.
∑
δ
(
u
i
,
v
i
)
∑
w
(
V
i
)
;
V
i
,
u
i
,
v
i
∈
G
′
.
值最大（
G
′
G’
G
′
必须联通）。
仔细思考发现我们选出的子图一定有如下性质：
- 一定为一棵树。
- 只有一条边。
性质①的证明：
假设我们已经选出了一棵树，目前的答案为
ρ
\rho
ρ
,那我们加上一条边
e
e
e
，这棵树一定会形成一个环，设此时的答案为
ρ
′
\rho’
ρ
′
。则易得
ρ
′
=
∑
w
(
V
i
)
∑
δ
(
u
i
,
v
i
)
+
δ
(
e
)
<
ρ
\rho’=\frac{\sum w(V_i)}{\sum{\delta(u_i,v_i)+\delta(e)}}<\rho
ρ
′
=
∑
δ
(
u
i
,
v
i
)
+
δ
(
e
)
∑
w
(
V
i
)
<
ρ
所以不加边一定比加边更优,最后的最优解的形态一定是树。
性质②的证明：
我们选出一条边
e
1
(
u
,
v
)
e_1(u,v)
e
1
(
u
,
v
)
后答案显然是
ρ
=
w
(
u
)
+
w
(
v
)
δ
(
u
,
v
)
\rho=\dfrac{w(u)+w(v)}{\delta(u,v)}
ρ
=
δ
(
u
,
v
)
w
(
u
)
+
w
(
v
)
，这时我们再添加一条边
e
2
(
v
,
k
)
e_2(v,k)
e
2
(
v
,
k
)
，使图结构仍然为树,此时答案显然是
ρ
′
=
w
(
u
)
+
w
(
v
)
+
w
(
k
)
δ
(
u
,
v
)
+
δ
(
v
,
k
)
\rho’=\dfrac{w(u)+w(v)+w(k)}{\delta(u,v)+\delta(v,k)}
ρ
′
=
δ
(
u
,
v
)
+
δ
(
v
,
k
)
w
(
u
)
+
w
(
v
)
+
w
(
k
)
.
作差得：
ρ
−
ρ
′
=
(
w
(
u
)
+
w
(
v
)
)
∗
δ
(
v
,
k
)
−
w
(
k
)
∗
δ
(
u
,
v
)
(
δ
(
u
,
v
)
+
δ
(
v
,
k
)
)
∗
δ
(
u
,
v
)
\rho-\rho’=\dfrac{(w(u)+w(v))*\delta(v,k)-w(k)*\delta(u,v)}{(\delta(u,v)+\delta(v,k))*\delta(u,v)}
ρ
−
ρ
′
=
(
δ
(
u
,
v
)
+
δ
(
v
,
k
)
)
∗
δ
(
u
,
v
)
(
w
(
u
)
+
w
(
v
)
)
∗
δ
(
v
,
k
)
−
w
(
k
)
∗
δ
(
u
,
v
)
若要使答案更优，则上式应该小于零，即：
w
(
k
)
δ
(
v
,
k
)
>
ρ
\dfrac{w(k)}{\delta(v,k)}>\rho
δ
(
v
,
k
)
w
(
k
)
>
ρ
放缩得
ρ
(
e
2
)
>
ρ
(
e
1
)
\rho(e_2)>\rho(e_1)
ρ
(
e
2
)
>
ρ
(
e
1
)
所以我们应该之选密度最大的一条边。
代码如下：
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
const int SIZE=600;
int n,m;
double a[SIZE],c,ans=0;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
ans=max(ans,(a[u]+a[v])/w);
}
cout<<fixed<<setprecision(15)<<ans<<endl;
return 0;
}