Codeforces Global Round 24 : F. Doremy's Experimental Tree

これ以来CGRないの？
https://codeforces.com/contest/1764/problem/F

問題

重み付き辺を持つ木を成すグラフがある。
ここに以下の情報が与えられる。

• 2点i-j間に重さ1の辺を追加すると、閉路ができる。この時の各点から閉路中の点への最短距離の総和が与えられる。

元の木の辺を求めよ。

解法

点0から始めて、プリム法に近い感じで頂点を追加していこう。

int N;
ll F[2020][2020];
vector<int> E[2020];
vector<pair<pair<int,int>,ll>> Es;

int dfs(int cur,int pre) {
	int C=1;
	
	FORR(e,E[cur]) if(e!=pre) {
		C+=dfs(e,cur);
	}
	FORR(e,E[cur]) if(e==pre) {
		Es.push_back({{cur,pre},(F[pre][pre]-F[pre][cur])/C});
	}
	
	return C;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	set<int> L,R;
	FOR(x,N) {
		if(x) R.insert(x);
		FOR(y,x+1) {
			cin>>F[x][y];
			F[y][x]=F[x][y];
		}
	}
	L.insert(0);
	priority_queue<pair<ll,pair<int,int>>> Q;
	FOR(i,N) if(i) Q.push({F[0][i],{0,i}});
	while(R.size()) {
		//一番近いものを探す
		while(1) {
			auto p=Q.top();
			x=p.second.first;
			y=p.second.second;
			if(L.count(x)&&L.count(y)) {
				Q.pop();
			}
			else {
				break;
			}
		}
		auto p=Q.top();
		x=p.second.first;
		y=p.second.second;
		Q.pop();
		E[x].push_back(y);
		E[y].push_back(x);
		R.erase(y);
		L.insert(y);
		FORR(r,R) Q.push({F[y][r],{y,r}});
	}
	dfs(0,-1);
	
	FORR2(a,b,Es) {
		cout<<a.first+1<<" "<<a.second+1<<" "<<b<<endl;
	}
}

まとめ

なんでCGRないんだろうな。