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
図の中の各ノードには、各エッジに重み値があり、そこからサブ図を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;
}