Codeforces 444 A DZY Loves Physics(図論)

3361 ワード

タイトルリンク:Codeforces 444 A DZY Loves Physics
図の中の各ノードには、各エッジに重み値があり、そこからサブ図を1枚選び、サブ図を連通させ、選択された任意の2点があり、エッジが存在する場合は、必ず選択されます.ポイントの重み値とエッジの重み値と最大はいくらですか.
問題を解く構想:図論の中の1つの結論で、最大2つのノードなので、2つの辺を列挙すればいいです.簡単に押してみましたが、2点の場合は3点より優れているに違いありません.
3点a,b,c,重み値がそれぞれA,B,C現a−b,b−c辺の重み値がそれぞれu,vであると仮定すると,2点の場合A+Bu,B+CvでA+Bu≧B+Cvであると仮定すると,3点の場合A+B+Cu+vであり,(A+B)v≧(B+C)uでA+BuとA+B+Cu+vを比較すると,両側にu∗u同減(A+B)∗u,(A+B)∗vとC∗uは(A+B)∗v≧(B+C)∗u≧C∗u
#include <cstdio>
#include <cstring>
#include <algorithm>

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
"
, ans); return 0; }