题目链接

https://codeforces.com/problemset/problem/445/C

解题思路

题意：求一个图的最大密度，密度定义：为顶点的价值和/边的价值和
题解：一个图最大的密度只由两个顶点构成。

证明：V1和V2边价值为a，构成图的最大密度。

若加上与V2相连的一个顶点V3最大，边的价值为b，则要求：V3/b>(V1+V2)/a;那么（V2+V3）/b，就是较大的。所以最大密度就是由两个顶点比他们的边得到的。

详细证明：
已知：V3/b>(V1+V2)/a
=> a*V3>b*(V1+V2)
=> a*V3+a*V2>b*V1+b*V2
=> a*(V3+V2)>b*(V1+V2)
=> (V3+V2)/b>(V1+V2)/a
求将某点加入使得价值最大的必要条件：
V总：已加入点的价值和；
v：要加入点的价值；
E总：已加入边的价值和；
e：加入点与已加入点所有边的价值和。
将此点加入的必要条件为(V总+v)/(E总+e)>V总/E总
=> (V总+v)*E总>(E总+e)*V总
=> V总*E总+v*E总>E总*V总+e*V总
=> v*E总>e*V总
=> v/e>V总/E总
所以，“若加上与V2相连的一个顶点V3最大，边的价值为b，则要求：V3/b>(V1+V2)/a”

AC代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;
const int N=600;
int n,m,a,b;
double vv[N],c,ans;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%lf",&vv[i]);

    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%lf",&a,&b,&c);
        ans=max(ans,(vv[a]+vv[b])/c);
    }

    printf("%.15lf\n",ans);
}

总结

记住什么是图的最大密度
记住两点构成最大密度