yukicoder : No.1833 Subway Planning

こちらはすんなり解けたな。
https://yukicoder.me/problems/no/1833

問題

木を成す無向グラフが与えられる。
各辺には正整数からなるコストが付与されている。

このグラフに対し、1回だけ以下の処理を行える。

• 2頂点を選択し、その2頂点を結ぶパス上のコストの最小値をmとする。その後、パス上の全辺のコストをmだけ引く。

木の全辺のコストの最大値の最小値を求めよ。

解法

コストの最大値をv以下にできるか、2分探索をしよう。

コストがvより大きな辺を抽出し、それらを結ぶシュタイナー木を考える。

• それらがパスを成すなら、mが求められるので、実際にm引いた状態でvよりコストが大きな辺が残るか判定する。
• それらが分岐を持ち、パスとならないなら、v以下の達成不可。

シュタイナー木がパスを成すかどうかは、以下のように判定した。

• コストがvより大きな辺を1個選ぶ。
• その両端をx,yとすると、xを根とする(yと反対側の)subtreeと、yを根とする(xと反対側の)subtreeそれぞれにおいて、2つ以上の子がvより大きなコストを持たないことをDFSで確認する。

int N;
vector<pair<int,int>> E[202020];

pair<int,int> hoge(int cur,int pre,int v) {
	pair<int,int> p={1<<30,-1};
	FORR2(e,c,E[cur]) if(e!=pre) {
		auto q=hoge(e,cur,v);
		if(q.second>v||c>v) {
			q.first=min(q.first,c);
			q.second=max(q.second,c);
		}
		
		
		if(p.second>v&&q.second>v) {
			return {-1,1<<30};
		}
		else if(q.second>=v) {
			p=q;
		}
	}
	return p;
	
}


int can(int v) {
	int i;
	FOR(i,N) {
		FORR2(e,c,E[i]) if(c>v) {
			pair<int,int> A=hoge(e,i,v);
			pair<int,int> B=hoge(i,e,v);
			
			return (max({c,A.second,B.second})-min({c,A.first,B.first}))<=v;
		}
	}
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y>>r;
		E[x-1].push_back({y-1,r});
		E[y-1].push_back({x-1,r});
	}
	
	int ret=(1<<30)-1;
	for(i=29;i>=0;i--) if(can(ret-(1<<i))) ret-=1<<i;
	cout<<ret<<endl;
}

まとめ

実装はちょっと面倒だけど、方針はたちやすい問題。