445C - Codeforces Round #254 (Div. 2) CDZY Loves Physics

domen111

http://codeforces.com/contest/445/problem/C

這題程式非常簡單，應該算是會陣列就會寫的那種初學者等級的，不過要在比賽中想到做法算是有點難，我是上網看別人的說明才懂得。

題意: 要在一個圖中找出一個導出子圖，使得 點的數值總和/邊的數值總和 最大。 (大概敘述一下，詳細定義自己看)

想過一堆很麻煩的算法，其實答案的導出子圖一定是一條邊+那條邊連接的兩個點，O(m)掃過去，輕鬆AC(也不算輕鬆啦! 寫程式5分鐘，想做法n小時)。
比賽的時候有想到這個方向的作法，但沒有想出來這樣就是對了，真是可惜。 (網路上好像很多人也是這樣)

附上短短的code:

#include<iostream>

#include<algorithm>

#include<iomanip>

using namespace std;

int main()

{

    int n,m;

    cin>>n>>m;

    int v[n];

    for(int i=0;i<n;i++)

        cin>>v[i];

    double ans=0;

    for(int i=0;i<m;i++)

    {

        int a,b,c;

        cin>>a>>b>>c;

        a--; b--;

        ans=max(ans,double(v[a]+v[b])/c);

    }

    cout<<fixed<<setprecision(9)<<ans;

}

不是很嚴謹的證明:
1. 先思考如果完全不取任何點或只取一點有沒有可能-->因為題目的定義，沒有邊答案會是0，所以不可能。 (除非原圖只有一點)
2. 以下圖作為範例，原本只有取紅色的點和邊，考慮要不要把綠色加進來子圖。


如果只取紅色部分，答案為[tex]\frac{a+b}{e}[/tex]。
當[tex]\frac{c}{f}>\frac{a+b}{e}[/tex]時，[tex]\frac{a+b+c}{e+f}>\frac{a+b}{e}[/tex]，表示應該將綠色部分加入。
但會發現，這種情況不如取黑框部分，[tex]\frac{c+b}{f}[/tex]必大於[tex]\frac{c}{f}[/tex]