竹園論壇

標題: 445C - Codeforces Round #254 (Div. 2) CDZY Loves Physics [打印本頁]

作者: domen111 時間: 2014-7-7 16:48
標題: 445C - Codeforces Round #254 (Div. 2) CDZY Loves Physics
本帖最後由 domen111 於 2014-7-7 17:54 編輯

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]

歡迎光臨竹園論壇 (http://forum.tfcis.org/)