CF611H New Year and Forgotten Tree 题解

CF611H New Year and Forgotten Tree

题意

• 有一棵 $n$ 个节点的树，节点编号为 $1 \sim n$。
• 记录这棵树的方式是记录下每条边连接的两点的编号。
• 现在，你不知道这些编号具体是多少，你只知道它们在十进制下的位数。
• 请你构造出一棵满足要求的树，或判断没有满足要求的树。
• $n \le 2 \times 10^5$。

题解

不妨把位数相同的点称为同种颜色，则显然有 $m = \lfloor \log_{10} n \rfloor + 1$ 种颜色。

对于每种颜色选择一个关键点，可以发现，如果存在合法的树，一定存在一种情况，使得关键点连成一个连通块，其他点连向某一个关键点。

那么，我们可以 $\mathcal O(m^{m-2})$ 枚举 Prufer 序列得到关键点的连通方式，对于剩下的颜色边 $(x,y)$，我们可以将 $x$ 接到 $y$ 的关键点上，也可以将 $y$ 接到 $x$ 的关键点上。

这相当于要做一个二分图多重匹配：

1. 二分图的左部点为每种类型的边，一共有 $\frac{m(m+1)}2$ 个点，每个点的数量为原树对应的边的数量减去关键点之间对应的边的数量。
2. 二分图的右部点为每种颜色的点，一共有 $m$ 个点，每个点的数量为原树对应的点的数量减去关键点中对应的点的数量。
3. 对于颜色边 $(x,y)$，将其对应的左部点分别与 $x,y$ 对应的右部点连边，数量为 $+\infty$。

如果这个二分图存在多重完备匹配，则说明有解，否则无解。

那么跑一遍网络流即可判断，如果有解则可以直接根据残量网络构造。

由于 $m$ 非常小，所以可以不用考虑时间复杂度，保证正确性即可。

代码

namespace Dinic {
	const int N = 107, M = 1e3 + 7;
	const ll inf = 1e18;
	int n, m, S, T, h[N], hi[N], e[M], t[M], tot = 1, d[N];
	ll mxf, f[M];
	inline void add(int x, int y, ll z, int o = 1) {
		e[++tot] = y, f[tot] = z, t[tot] = h[x], h[x] = tot;
		if (o) add(y, x, 0, 0);
	}
	inline bool bfs() {
		for (int i = 1; i <= n; i++) d[i] = 0;
		queue<int> q;
		q.push(S), d[S] = 1;
		while (q.size()) {
			int x = q.front();
			q.pop();
			for (int i = h[x]; i; i = t[i]) {
				int y = e[i];
				ll z = f[i];
				if (d[y] || !z) continue;
				q.push(y), d[y] = d[x] + 1;
				if (y == T) return 1;
			}
		}
		return 0;
	}
	ll dinic(int x, ll nwf) {
		if (x == T) return nwf;
		ll rst = nwf;
		for (int &i = hi[x]; i; i = t[i]) {
			int y = e[i];
			ll z = f[i];
			if (d[y] != d[x] + 1 || !z) continue;
			ll k = dinic(y, min(z, rst));
			if (!k) d[y] = 0;
			else f[i] -= k, f[i^1] += k, rst -= k;
			if (!rst) break;
		}
		return nwf - rst;
	}
	inline void main() {
		while (bfs()) {
			for (int i = 1; i <= n; i++) hi[i] = h[i];
			ll now;
			while ((now = dinic(S, inf))) mxf += now; 
		}
	}
}

const int N = 2e5 + 7, M = 9;
int n, p[M], q[M], m, a[M], b[M], d[M], g[M];
char s[M];
map<pi, int> c, f;

inline void work() {
	for (int i = 1; i <= m; i++) d[i] = 0;
	for (int i = 1; i <= m - 2; i++) ++d[a[i]]; a[m-1] = m;
	map<pi, int> c = ::c;
	vector<pi> e;
	for (int i = 1, j = 1; i < m; i++, j++) {
		while (d[j]) ++j; e.pb(mp(j, a[i]));
		while (i < m && !--d[a[i]] && a[i] < j) e.pb(mp(a[i], a[i+1])), ++i;
	}
	for (pi o : e) {
		if (o.fi > o.se) swap(o.fi, o.se);
		if (!c[o]--) return;
	}
	Dinic::n = 2 + m + m * (m + 1) / 2;
	Dinic::S = Dinic::n - 1, Dinic::T = Dinic::n;
	Dinic::tot = 1, Dinic::mxf = 0;
	for (int i = 1; i <= Dinic::n; i++) Dinic::h[i] = 0;
	int k = m;
	vector<pi> ff(Dinic::n);
	for (int i = 1; i <= m; i++) {
		Dinic::add(i, Dinic::T, b[i]);
		for (int j = i; j <= m; j++) {
			f[mp(i,j)] = ++k, ff[k] = mp(i, j);
			Dinic::add(Dinic::S, k, c[mp(i,j)]);
			Dinic::add(k, i, Dinic::inf);
			Dinic::add(k, j, Dinic::inf);
		}
	}
	Dinic::main();
	if (Dinic::mxf != n - m) return;
	for (pi o : e) print(p[o.fi], ' '), print(p[o.se]);
	for (int x = 1; x <= m; x++) {
		q[x] = p[x];
		for (int i = Dinic::h[x]; i; i = Dinic::t[i]) {
			int y = Dinic::e[i];
			if (y <= m || y >= Dinic::S) continue;
			y = ff[y].fi == x ? ff[y].se : ff[y].fi;
			while (Dinic::f[i]--) print(++q[x], ' '), print(p[y]);
		}
	}
	exit(0);
}

void dfs(int o) {
	if (o == m - 1) return work();
	for (int i = 1; i <= m; i++) a[o] = i, dfs(o + 1);
}

int main() {
	rd(n);
	for (int o = 1; o <= n; o *= 10) p[++m] = o;
	for (int i = 1; i < m; i++) b[i] = p[i+1] - 1 - p[i];
	b[m] = n - p[m];
	for (int i = 1, x, y; i < n; i++) {
		rds(s, x), rds(s, y);
		if (x > y) swap(x, y);
		++c[mp(x,y)];
	}
	if (m == 1) {
		if (c[mp(1,1)] != n - 1) return print(-1), 0;
		for (int i = 1; i < n; i++) print(i, ' '), print(i + 1);
		return 0;
	}
	dfs(1), print(-1);
	return 0;
}