IOI2020连接擎天树题解

题意:一个 nn 个点的图,给定了任意两点之间的不同简单路数量 aija_{ij},简单路定义为不经过重复点的路径,保证0aij30\le a_{ij}\le 3。求构造满足要求的图或判断无解。

画几张图观察一下简单路的性质,发现合法的图一定满足任意一个连通块中最多只有一个环。如果一个连通块有不止一个环,一定可以找到一对点存在至少四条不同简单路,如下图:

那么一个连通块一定是树或者基环树。dfs 出每个连通块,先判断一下如果连通块里出现了路径数为 00 的点对就是无解。然后树非常好处理,如果连通块内路径数全是 11 那就是树,随便构造一个就行。基环树复杂一些,我们画张图:

观察发现,如果两个点在同一个红圈里,那它们只间有 11 条简单路,否则有 22 条。33 是绝对不会出现的,出现了直接无解。然后 dfs 出每个连通块里,由 aij=1a_{ij}=1 相连的子连通块,它们应该在一个红圈里。如果一个红圈里混进了路径数为 22 的点对那无解,否则把它们连成一棵树。最后在每个红圈里找一个代表点,把这些代表点串起来成为一个环即可。如果代表点不足三个就没法串成环,还是无解。

#include "supertrees.h"
#define N 1000
std::vector<std::vector<int>> *G, ret;
void addedge(int x, int y) {
	ret[x][y] = ret[y][x] = 1;
}
int n, mx; char vis[N];
std::vector<int> cnt, all, sm;
void dfs(int x) {
	vis[x] = 1;
	cnt.push_back(x);
	for (int i = 0; i < n; i++) {
		int d = (*G)[x][i];
		mx = std::max(d, mx);
		if (!vis[i] && d) dfs(i);
	}
}
void dfsS(int x) {
	vis[x] = 2;
	sm.push_back(x);
	for (int i = 0; i < n; i++) {
		if (vis[i] == 1 && (*G)[x][i] == 1) dfsS(i);
	}
}
int construct(std::vector<std::vector<int>> p) {
	G = &p; n = p.size();
	ret.resize(n);
	for (int i = 0; i < n; i++)
		ret[i].resize(n);
	for (int i = 0; i < n; i++) if (!vis[i]) {
		mx = 1;
		cnt.clear();
		dfs(i);
		if (mx == 3) return 0;
		for (int i = 1; i < cnt.size(); i++)
			for (int j = 0; j < i; j++)
				if (p[cnt[i]][cnt[j]] == 0)
					return 0;
		if (mx == 1) {
			for (int i = 1; i < cnt.size(); i++)
				addedge(cnt[0], cnt[i]);
			continue;
		}
		all.clear();
		for (int j : cnt) if (vis[j] == 1) {
			sm.clear();
			dfsS(j);
			for (int i = 1; i < sm.size(); i++) {
				for (int j = 0; j < i; j++)
					if (p[sm[i]][sm[j]] != 1)
						return 0;
				addedge(sm[0], sm[i]);
			}
			all.push_back(sm[0]);
		}
		if (all.size() <= 2) return 0;
		for (int j = 1; j < all.size(); j++)
			addedge(all[j-1], all[j]);
		addedge(all[0], all.back());
	}
	build(ret);
	return 1;
}