これはどういうイベントだ?
https://community.topcoder.com/stat?c=problem_statement&pm=15336
問題
重み付無向辺からなる木を成すグラフが与えられる。
ここから、同一の重みwの辺だけからなるパスを選択し、パス上の辺を削除する、という処理を行う。
この時かかるコストは、パスの長さによらずwである。
最適なパス選択をおこなう場合、全ての辺を消すまでの総コストの最小値を求めよ。
解法
辺を重み別に分類し、それぞれ処理していこう。
個々の重みについての処理は単純で、次数1の頂点を見つけたら、そこから貪欲に行けるところまでパスを伸ばし削除する、という処理を行えばよい。
パスを伸ばす方向は無理に決めなくても、貪欲に選択すれば最小値になる。
class DismantleTheTree { set<int> E[101][1001]; public: void dfs(int cur,int w) { if(E[w][cur].empty()) return; auto a=*E[w][cur].begin(); E[w][cur].erase(a); E[w][a].erase(cur); dfs(a,w); } int dismantle(int N, vector <int> X, vector <int> Y, vector <int> weight) { int i,x,y; set<int> is[101]; FOR(x,101) FOR(y,1001) E[x][y].clear(); FOR(i,N-1) { E[weight[i]][X[i]-1].insert(Y[i]-1); E[weight[i]][Y[i]-1].insert(X[i]-1); is[weight[i]].insert(X[i]-1); is[weight[i]].insert(Y[i]-1); } int ret=0; FOR(x,101) { FOR(y,1001) { FORR(i,is[x]) if(E[x][i].size()==1) { ret+=x; dfs(i,x); is[x].erase(i); } } } return ret; } }
まとめ
これ難易度はDiv2とDiv1の間ぐらい?