kmjp's blog

競技プログラミング参加記です

TopCoder 2019 Humblefool Cup Prelims : Div1 Medium DismantleTheTree

これはどういうイベントだ?
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の間ぐらい?