Codeforces #254 Div1 A. DZY Loves Physics

久々のCodeforces。Aを落としたけどBCを解ききって赤に戻れたのでよかった。
http://codeforces.com/contest/444/problem/A

問題

無向辺のグラフが与えられる。
各頂点にはスコアV[i]、各辺にはスコアE[i]が正の整数で振られている。

このグラフの連結した部分グラフのうち、(V[i]の総和)/(E[i]の総和)の最大値を求めよ。

解法

頂点をp個選ぶには辺を(p-1)個選ばなければならない。
よって(V[i]の総和)/(E[i]の総和)を最大にするにはp=2であることが望ましい。

後は全部の辺において(辺の両端の頂点のV[i]の和)/E[i]の最大を求めればよい。

int N,M;
int X[1001];
int mat[501][501];

void solve() {
	int f,i,j,k,l,x,y;
	MINUS(mat);
	cin>>N>>M;
	FOR(i,N) cin>>X[i];
	double ma=0;
	FOR(i,M) {
		cin>>x>>y>>j;
		ma=max(ma,(X[x-1]+X[y-1]+0.0)/j);
	}
	_P("%.12lf\n",ma);
}

まとめ

本番無駄にDFSとかやってミス。
時間も無駄にしてしまった。