题目大意：给出一张图，图中的每一个节点，每条边都有一个权值。如今有从中挑出一张子图，要求子图联通，而且被选中的随意两点。假设存在边，则一定要被选中。问说点的权值和/边的权值和最大是多少。

解题思路：是图论中的一个结论，最多两个节点。所以枚举两条边就能够了。我简单的推了一下，2个点的情况肯定比3个点的优。

如果有3个点a，b，c,权值分别为A，B。C

现a-b，b-c边的权值分别为u。v

那么对于两点的情况有A+Bu,B+Cv

如果有A+Bu≥B+Cv

对于三点来说A+B+Cu+v,有(A+B)∗v≥(B+C)∗u

比較A+Bu和A+B+Cu+v,两边同乘u∗(u+v),得(A+B)∗(u+v)和(A+B+C)∗u

同减(A+B)∗u。(A+B)∗v和C∗u

由于(A+B)∗v≥(B+C)∗u≥C∗u

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn = 500;int n, m;double val[maxn+5];int main () {    scanf("%d%d", &n, &m);    for (int i = 1; i <= n; i++)        scanf("%lf", &val[i]);    double ans = 0, k;    int a, b;    for (int i = 0; i < m; i++) {        scanf("%d%d%lf", &a, &b, &k);        double tmp = (val[a] + val[b]) / k;        if (tmp > ans)            ans = tmp;    }    printf("%.15lf\n", ans);    return 0;}
       
      
     

版权声明：本文博主原创文章，博客，未经同意不得转载。