看出类似 Hall
定理的结论后就在向网络流上靠，结果连基本的剥叶子构造都忘记了。
我们将每种位数看成一种颜色，问题就是给出每种颜色的点集大小与颜色两两之间的边集大小，还原出一棵树。
首先判断题目给出的东西是否有解，可以用类似 Hall
定理的思路，枚举一个颜色子集 \(S\)，那么 \(S\) 的导出子图的边数必须小于 \(S\)
中的点数，必要性显然，充分性不会证。感性理解，对于一棵树，如果枚举树上的点集然后检查这个条件，那么这是充要的。但现在我们因为知道的信息不够多，只能枚举每个颜色集合，大胆猜测这也是充要的。
基于此直接剥叶子即可。枚举叶子所在的颜色 \(i\) 和叶子父亲所在的颜色 \(j\)，删掉这一条边后再 Check 即可。如果
Check 成功，就将 \(i\)
中编号最大的点连向 \(j\)
中编号最小的点（这个编号最大与最小不是必然的，只是我们需要对每个颜色选定一个接收其它颜色连边的关键点，同时保证这个关键点最后被删掉）。
做到最后，可能两个不同的颜色 \(i,j\)
之间还存在一条边，直接连过去即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5,M = 10;
int n,m;
int a[M][M],b[M];
inline bool Check() {
for(int i = 1;i < (1 << m);i++) {
int sm = 0,sn = 0;
for(int j = 1;j <= m;j++)
if((i >> j - 1) & 1) sn += b[j];
for(int j = 1;j <= m;j++)
for(int k = j;k <= m;k++)
if(((i >> j - 1) & 1) && ((i >> k - 1) & 1)) sm += a[j][k];
if(sm >= sn) return false;
}
return true;
}
int pp[M];
int Sum;
inline bool Reduce() {
for(int i = 1;i <= m;i++)
for(int j = 1;j <= m;j++) {
if(a[i][j] >= 1 && b[i] > 1) {
a[i][j]--;b[i]--;
if(Check()) return printf("%d %d\n",pp[i] + b[i],pp[j]),++Sum,true;
a[i][j]++;b[i]++;
}
if(a[i][j] >= 1 && b[j] > 1) {
a[i][j]--;b[j]--;
if(Check()) return printf("%d %d\n",pp[i],pp[j] + b[j]),++Sum,true;
a[i][j]++;b[j]++;
}
}
return false;
}
int main() {
cin >> n;m = (int)log10(n) + 1;
for(int i = 1;i < n;i++) {
string s1,s2;
cin >> s1 >> s2;
if(s1.size() > s2.size()) swap(s1,s2);
a[s1.size()][s2.size()]++;
}
pp[1] = 1;
for(int i = 2;i <= m;i++) pp[i] = 10 * pp[i - 1];
for(int i = 1;i < m;i++) b[i] = pp[i + 1] - pp[i];
b[m] = n - pp[m] + 1;
if(!Check()) return puts("-1"),0;
while(Reduce());
for(int i = 1;i <= m;i++)
for(int j = i + 1;j <= m;j++)
if(a[i][j]) printf("%d %d\n",pp[i],pp[j]),++Sum;
assert(Sum == n - 1);
return 0;
}
|