CF 1714 F

标签：rt nxt emplace 1714 int back CF ans

我来力！（喜）
本题作为比赛中最难的题，其地位堪比 Igallta 。（什

题面

这里空空如也，什么也没有哦 ~

思路

设 $ x = d_{12}, y = d_{31}, z = d_{23} $，解三元一次方程组

\[\begin{cases} a + b = x \\ a + c = y \\ b + c = z \end{cases} \]

$ a, b, c $ 分别代表 $ 1 $ 到根的距离，$ 2 $ 到根的距离，$ 3 $ 到根的距离。
设根为 $ r $ 。

• 如果 $ a = 0 $ ，则 $ r = 1 $；
• 如果 $ b = 0 $ ，则 $ r = 2 $；
• 如果 $ c = 0 $ ，则 $ r = 3 $；
• 如果每个都不成立，则 $ r = 4 $。

接着，我们从 $ r $ 开始，不断连一个空闲节点，最后把最后一个用的节点连到 $ 1 $ ，$ 2 $ 或 $ 3 $ 。
完成。

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int> > ans;

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		ans.clear();
		int n, x, y, z;
		scanf("%d %d %d %d", &n, &x, &z, &y);
		bool flag = 1;
		int abc = (x + y + z) / 2;
		if (abc * 2 != x + y + z) {
			flag = 0;
		}
		int a = abc - z, b = abc - y, c = abc - x;
		if (a + b + c >= n) {
			flag = 0;
		}
		int rt;
		if (a == 0) rt = 0;
		else if (b == 0) rt = 1;
		else if (c == 0) rt = 2;
		else rt = 3;
		int nxt = (rt == 3) ? (3) : (2);
		
		flag &= ((a >= 0) && (b >= 0) && (c >= 0));
		
		if (a) {
			if (a == 1) {
				ans.emplace_back(rt, 0);
			} else {
				ans.emplace_back(rt, ++nxt);
				for (int i = 1; i < a - 1; i++) {
					ans.emplace_back(nxt, nxt + 1);
					nxt++;
				}
				ans.emplace_back(nxt, 0);
			}
		}
		
		if (b) {
			if (b == 1) {
				ans.emplace_back(rt, 1);
			} else {
				ans.emplace_back(rt, ++nxt);
				for (int i = 1; i < b - 1; i++) {
					ans.emplace_back(nxt, nxt + 1);
					nxt++;
				}
				ans.emplace_back(nxt, 1);
			}
		}
		if (c) {
			if (c == 1) {
				ans.emplace_back(rt, 2);
			} else {
				ans.emplace_back(rt, ++nxt);
				for (int i = 1; i < c - 1; i++) {
					ans.emplace_back(nxt, nxt + 1);
					nxt++;
				}
				ans.emplace_back(nxt, 2);
			}
		}
		
		while (nxt < n - 1) {
			ans.emplace_back(rt, ++nxt);
		}
		
		if (flag) {
			puts("YES");
			for (auto edge : ans) {
				printf("%d %d\n", edge.first + 1, edge.second + 1);
			}
		} else {
			puts("NO");
		}
	}
	return 0;
}

Bye！！！

标签：rt,nxt,emplace,1714,int,back,CF,ans
From： https://www.cnblogs.com/AProblemSolver/p/16743178.html