Algoogle

Algorithm for Programming Contest

Codeforces 444A DZY Loves Physics

Category: Codeforces Tag: math

DZY Loves Physics

問題概要


辺と頂点に重さのあるグラフGが与えられる(連結とは限らない)
このグラフの部分グラフHを考える.
ただしHは連結で, それに含まれる頂点同士にGで辺が存在する場合は必ずHにもその辺が含まれる. そのようなHのうち(頂点の重さの総和)/(辺の重さの総和)の最大を求めよ

解法


最適な場合は辺1つの場合(存在しない場合は0).
ある連結な頂点を共有せず, 互いに対して辺をもつグラフAとBを考える.
AとBの頂点の重さと辺の重さをそれぞれ(v,e), (w,f)とする.
またAとBを繋ぐ時に増える辺の重さをgとする.
これらを連結したほうが良い場合というのは以下の2式が共に成り立つ場合になる.

この2式を変形すると

これから

が導かれる. これはgが1以上であるので矛盾する. よって連結したほうが良い場合は存在しない.

コード


(444A.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

int n, m, u, v, c, x[512];

double solve()
{
        double ans = 0;
        for (int i = 0; i < n; i++) scanf("%d", x+i+1);
        while(m--){
                scanf("%d%d%d", &u, &v, &c);
                ans = max(ans, 1.*(x[u]+x[v])/c);
        }
        return ans;
}

int main()
{
        scanf("%d%d", &n, &m);
        printf("%.12f\n", solve());
        return 0;
}

Comments