TopCoder SRM 695 Div1 Medium BearKRoads

これは思いつかんなぁ。
https://community.topcoder.com/stat?c=problem_statement&pm=14364

問題

N頂点M無向辺からなるグラフが与えられる。
また各頂点にはスコアX[i]が与えられている。
各頂点は３本以上の辺をもたない。

ここでM辺からK個の辺を選んだ時、少なくとも１本以上の辺につながれているiのスコアの総和の最大値を求めよ。

解法

辺の両端の頂点の総和の降順で辺を並べよう。
例えば頂点u-vをつなぐ辺のスコアX[u]+X[v]が最大だとする。
この場合、u,vどちらも辺につながないことはありえない(他の辺を選ぶより、u-vをつなぐ辺の方が確実にスコアが増加するため)
そのため、u,vとつながる辺計5本のうち、最低１本は選択される。

このため、以下の何れかの方法でこの問題を解くことができる。

• 最大スコアの辺を求めてそこからつながる最大5本の辺のうち1本を選ぶ、ということをK回繰り返す。5^K回のDFSで済む。
• 選ばれるのは最大でもスコアが上位5*K位までの辺である。よって最初に辺の候補を5*K本まで絞りそこから5本選ぶ。通りの辺の選びかたを総当たりする。

class BearKRoads {
	public:
	vector<pair<int,int>> E;
	vector<int> X;
	
	int dfs(int cur,int left,int sum) {
		if(cur==E.size() || left==0) return sum;
		
		int ma=dfs(cur+1,left,sum);
		int a=X[E[cur].first];
		int b=X[E[cur].second];
		X[E[cur].first] = 0;
		X[E[cur].second] = 0;
		ma=max(ma,dfs(cur+1,left-1,sum+a+b));
		X[E[cur].first] = a;
		X[E[cur].second] = b;
		return ma;
	}
	
	int maxHappy(vector <int> x, vector <int> a, vector <int> b, int K) {
		int i;
		X=x;
		vector<pair<int,int>> V;
		FOR(i,a.size()) V.push_back({x[a[i]]+x[b[i]],i});
		
		sort(V.begin(),V.end());
		reverse(V.begin(),V.end());
		
		if(V.size()>5*K) V.resize(5*K);
		E.clear();
		FORR(r,V) E.push_back({a[r.second],b[r.second]});
		
		return dfs(0,K,0);
	}
}

まとめ

どちらもそこそこの計算量になるのが面白いね。