【Codeforces 611H】New Year and Forgotten Tree
mrsrz
1月 15, 2020
搜索，最大流。
题目大意：
给定一棵 $n$ 个点的树，告诉你每条边连接的两个点的编号的位数分别是多少，要求还原这棵树。输出任意方案。
题解：
位数相同的点之间是没有区别的，我们放在一起考虑。则最多有 $6$ 种不同位数。
对于相同位数的点，它们之间的连边，相当于把两个点缩成了一个点，也是没有区别的，所以可以任意连，每个连通块保留一个点和其他点相连即可。
考虑把每个不同的位数都取出一个结点作为主要结点，其他结点只作为叶子连在主要结点上。由于原图是一棵树，所以主要结点之间的连边形成一棵树。
由于不同连边方式很少，所以我们可以枚举这棵树的形态，然后考虑把剩下的结点连上去。
我们记录 $e[u][v]$ 表示位数为 $u$ 和 $v$ 的点之间还差多少条边。有两种方式连边：取出位数为 $u$ 的点，连向位数为 $v$ 的主要结点；或者反之。
相当于每个位数有一些点，需要去匹配它要连的点，以满足连边的需求。
我们可以用最大流来完成这个匹配的过程。当满流的时候，说明有合法方案。
输出方案在最大流的残量网络上不难构造。
细节较多。
Code：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=114;
int n,len,LST[8];
queue<int>q;
int eu[20],ev[20],cnt,fa[8],t0t[8],es[8][8],dep[N];
int id[2][33];
vector<int>num[8];
inline int find(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;}
struct edge{
int to,nxt,cap;
}e[N<<1];
int head[N],cnT,T,iter[N];
inline int addedge(int u,int v,int cap){
e[++cnT]=(edge){v,head[u],cap},head[u]=cnT;
e[++cnT]=(edge){u,head[v],0},head[v]=cnT;
return cnT;
}
bool chk(int zt){
for(int i=1;i<=len;++i)fa[i]=i;
for(int i=0;i<cnt;++i)
if(zt>>i&1){
int x=find(eu[i]),y=find(ev[i]);
if(x==y)return 0;
fa[y]=x;
}
return 1;
}
bool bfs(){
memset(dep,0,sizeof dep);
*dep=1;
for(q.push(0);!q.empty();){
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt)
if(e[i].cap&&!dep[e[i].to]){
dep[e[i].to]=dep[u]+1;
q.push(e[i].to);
}
}
return dep[T];
}
int dfs(int u,int f){
if(u==T||!f)return f;
for(int&i=iter[u];i;i=e[i].nxt)
if(e[i].cap&&dep[e[i].to]>dep[u]){
int d=dfs(e[i].to,min(e[i].cap,f));
if(d){
e[i].cap-=d,e[i^1].cap+=d;
return d;
}
}
return 0;
}
void output(int S){
for(int i=1;i<=len;++i){
vector<int>&vec=num[i];
for(int j=1;j<=es[i][i];++j){
int a=vec.back();vec.pop_back();
int b=vec.back();
printf("%d %d\n",a,b);
}
LST[i]=vec.back();
vec.pop_back();
}
for(int i=0;i<cnt;++i)if(S>>i&1)
printf("%d %d\n",LST[eu[i]],LST[ev[i]]);
for(int i=0;i<cnt;++i){
int x=id[0][i],u=eu[i],v=ev[i];
for(int k=e[x].cap;k;--k){
int a=num[u].back();
num[u].pop_back();
printf("%d %d\n",a,LST[v]);
}
x=id[1][i],u=ev[i],v=eu[i];
for(int k=e[x].cap;k;--k){
int a=num[u].back();
num[u].pop_back();
printf("%d %d\n",a,LST[v]);
}
}
}
int main(){
scanf("%d",&n);
len=log10(n)+1;
for(int i=1;i<n;++i){
char a[8],b[8];
scanf("%s%s",a,b);
int x=strlen(a),y=strlen(b);
if(x>y)swap(x,y);
++es[x][y];
}
for(int i=1;i<=n;++i)
if(i<10)++t0t[1],num[1].push_back(i);else
if(i<100)++t0t[2],num[2].push_back(i);else
if(i<1000)++t0t[3],num[3].push_back(i);else
if(i<10000)++t0t[4],num[4].push_back(i);else
if(i<100000)++t0t[5],num[5].push_back(i);else++t0t[6],num[6].push_back(i);
for(int i=1;i<=len;++i)if((t0t[i]-=es[i][i]+1)<0){
puts("-1");
return 0;
}
for(int i=1;i<=len;++i)
for(int j=i+1;j<=len;++j)
eu[cnt]=i,ev[cnt++]=j;
int sm=0;
for(int i=1;i<=len;++i)sm+=t0t[i];
for(int S=0;S<1<<cnt;++S)
if(__builtin_popcount(S)==len-1&&chk(S)){
for(int i=0;i<cnt;++i)
if(S>>i&1)--es[eu[i]][ev[i]];
bool ok=1;
for(int i=0;i<cnt;++i)
if(es[eu[i]][ev[i]]<0)ok=0;
if(!ok){
for(int i=0;i<cnt;++i)
if(S>>i&1)++es[eu[i]][ev[i]];
continue;
}
cnT=1;
memset(head,0,sizeof head);
T=len+cnt+1;
for(int i=1;i<=len;++i)
addedge(0,i,t0t[i]);
for(int i=0;i<cnt;++i){
int u=eu[i],v=ev[i];
id[0][i]=addedge(u,i+1+len,n);
id[1][i]=addedge(v,i+1+len,n);
addedge(i+1+len,T,es[eu[i]][ev[i]]);
}
int flow=0;
while(bfs()){
memcpy(iter,head,sizeof iter);
while(int f=dfs(0,1919810))flow+=f;
}
for(int i=0;i<cnt;++i)
if(S>>i&1)++es[eu[i]][ev[i]];
if(flow!=sm)continue;
output(S);
return 0;
}
puts("-1");
return 0;
}