New Year and Forgotten Tree[CF611H]

发表于 分类于

题目链接

CF

题解

首先简化一下，将位数相同的点搞在一起形成一个大的点，那么一共就有 $m=\left \lfloor \log_{10}n \right \rfloor \leq 6$ 个大点。对于每个大点，随便选择一个点作为关键点。

如果有解，那么肯定存在一种情况，使得一条原树中的边，其中一个点连向的是关键点。

那么关键点之间形成的，是一个树结构。

根据prufer数列，我们有 $m^{m-2}$ 种树。

那么暴力枚举所有的情况，考虑剩下的边怎么连。

也就是说，一条边 $(x,y)$ 有两种选择，要么 $x$ 连的是关键点，要么 $y$ 连。

建立一个二分图，左边的点代表剩下的边，右边的点代表一个大点。

然后建这个二分图，判断是否存在完美匹配，如果存在就找到一个解了。

判断是否存在完美匹配可以用Hall定理或者暴力跑网络流。

因为要输出方案，可以跑一个网络流，然后根据残量网络输出即可。

时间复杂度 $O(m^{m-2}2^m+m^3)$。

程序

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int inf=1e8;
const int M=1000;
namespace Dinic{
	int s,t;
	int ver[M],ne[M],head[M],val[M],tot=1;
	int cur[M],d[M];
	inline void add(int x,int y,int z)
	{
		ver[++tot]=y; val[tot]=z; ne[tot]=head[x]; head[x]=tot;
		ver[++tot]=x; val[tot]=0; ne[tot]=head[y]; head[y]=tot;
	}
	queue<int> q;
	inline bool bfs()
	{
		for(;!q.empty();q.pop());
		fo(i,s,t) d[i]=-1,cur[i]=head[i];
		q.push(s); d[s]=0;
		for(int u;!q.empty();)
		{
			u=q.front(); q.pop();
			for(int i=head[u],v;i;i=ne[i])
				if(d[v=ver[i]]==-1&&val[i])
				{
					d[v]=d[u]+1;
					q.push(v);
					if(v==t) return 1;
				}
		}
		return 0;
	}
	int dfs(int u,int flow)
	{
		if(!flow||u==t) return flow;
		int res=flow,v,r;
		for(int &i=cur[u];i;i=ne[i])
			if(val[i]&&d[v=ver[i]]==d[u]+1)
			{
				r=dfs(v,min(res,val[i]));
				if(!r) continue;
				res-=r; val[i]-=r; val[i^1]+=r;
				if(!res) break;
			}
		return flow-res;
	}
	void dinic()
	{
		for(;bfs();dfs(s,inf));
	}
}
using namespace Dinic;

int n,m,E[7][7],sum[7],pw[7],fa[7],id[100][2];
void work()
{
	ff(i,1,m) E[i][fa[i]]--,E[fa[i]][i]--;
	s=0;
	int k=m;
	ff(i,0,m)
		ff(j,i,m)
			if(E[i][j])
			{
				++k;
				id[k][0]=i,id[k][1]=j;
				add(s,k,E[i][j]);
				add(k,i+1,inf);
				add(k,j+1,inf);
			}
	t=k+1;
	ff(i,0,m) add(i+1,t,sum[i]-1);
	dinic();
	ff(i,1,m) printf("%d %d\n",pw[i],pw[fa[i]]);
	fo(u,1,m)
	{
		int now=1;
		for(int i=head[u],v;i;i=ne[i])
			if((v=ver[i])!=t)
			{
				int j=(u-1)^id[v][0]^id[v][1];
				fo(tim,1,val[i]) printf("%d %d\n",pw[u-1]+now,pw[j]),now++;
			}
	}
}
inline void check()
{
	static int f[1<<6],g[1<<6];
	cle(f); cle(g);
	ff(i,0,m) g[1<<i]=sum[i]-1;
	ff(i,0,m)
		ff(j,i,m)
			f[1<<i]+=E[i][j],f[1<<j]+=E[i][j],
			f[(1<<i)|(1<<j)]-=E[i][j];
	ff(i,1,m)
		f[1<<i]--,f[1<<fa[i]]--,
		f[(1<<i)|(1<<fa[i])]++;
	ff(s,1,1<<m)
	{
		if(lowbit(s)^s)
		{
			f[s]+=f[lowbit(s)]+f[s^lowbit(s)];
			g[s]+=g[lowbit(s)]+g[s^lowbit(s)];
		}
		if(f[s]<g[s]) return;
	}
	work();
	exit(0);
}

void dfs(int u)
{
	if(u==m)
	{
		ff(i,1,m)
		{
			int x=i;
			ff(j,1,m) x=fa[x];
			if(x) return;
		}
		check();
		return;
	}
	ff(i,0,m)
		if(u!=i&&E[u][i])
		{
			fa[u]=i;
			dfs(u+1);
			fa[u]=0;
		}
}

int main()
{
	scanf("%d",&n);
	char s1[10],s2[10];
	int u,v;
	fo(i,2,n)
	{
		scanf("%s%s",s1,s2);
		u=strlen(s1)-1; v=strlen(s2)-1;
		E[u][v]++;
		if(u^v) E[v][u]++;
	}
	m=0;
	for(int i=1;i<=n;i*=10,m++) sum[m]=min(i*10,n+1)-i,pw[m]=i;
	dfs(1);
	printf("-1\n");
	return 0;
}