CPSCO2019 Session4 : F - Lost Tree

なんとか解けて良かった。
https://atcoder.jp/contests/cpsco2019-s4/tasks/cpsco2019_s4_f

問題

N頂点の木を成す距離付の無向グラフを構成せよ。
そのうち最初のK点については、全頂点間の距離が与えられる。
また、その距離に対し矛盾のないグラフが作れることが保障される。

解法

頂点番号1から始め、そこから距離の短い順に頂点と辺をグラフに追加していこう。
場合によっては、設置済みの辺を分割するケースがある(サンプル1で、頂点3を追加することを考える)。
この場合、そこに(N+1)番以降の頂点を挿入すればよい。

int K;
ll D[1010][1010];

int nex;
vector<vector<int>> E[1010];
ll F[1010];
vector<pair<int,int>> P;

void dfs(int cur,int tar) {
	FORR(e,E[cur]) {
		ll sp=(F[tar]+F[e[1]]-D[e[1]][tar])/2;
		
		if(sp>=F[e[0]]) {
			dfs(e[0],tar);
			return;
		}
		if(sp<=F[cur]) {
			continue;
		}
		
		//add
		F[nex]=sp;
		E[nex].push_back({e[0],e[1]});
		E[nex].push_back({tar,tar});
		e[0]=nex;
		nex++;
		return;
	}
	
	E[cur].push_back({tar,tar});
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K;
	nex=K;
	FOR(y,K) FOR(x,K) cin>>D[y][x];
	FOR(y,K) {
		F[y]=D[0][y];
		if(y!=0) P.push_back({F[y],y});
	}
	sort(ALL(P));
	FORR(p,P) dfs(0,p.second);
	
	cout<<nex<<endl;
	FOR(i,nex) FORR(e,E[i]) cout<<(i+1)<<" "<<(e[0]+1)<<" "<<(F[e[0]]-F[i])<<endl;
	
	
	
}

まとめ

これでCPSCO終了です、お疲れ様でした。