[USACO23OPEN] Tree Merging G 题解

前言

赛时只打出了特殊性质，还是太菜了 /kk。

解法

以下描述中，“原始状态”指的是未进行任何合并操作的树，“目标状态”指的是“进行完所有合并操作后的树”，

K_1(a)

表示节点

a

在“原始状态”中的子节点集合，

K_2(a)

表示节点

a

在“目标状态”中的子节点集合，

w_a

表示在目标状态中不存在的节点在操作过程中和它进行合并的节点。

令

c_{a,b}

为“节点

a

是否可以合并进节点

b

”。显然的，若

c_{a,b}

为真，那么

a

和

b

必须满足以下几个条件：

目标状态包含节点 $b$ ；
$a\le b$ ，等号能取到当且仅当目标状态包含节点 $a$ ；
$\forall i\in K_1(a)$ ， $\exists j\in K_2(b)$ 使得 $c_{i,j}$ 为真。

计算出

c_{a,b}

不是难事，可以根据定义，从树的叶子节点开始按照深度递减一直算到根节点即可。

最后构造方案时，从根节点开始按照深度递增一直算到叶子节点，枚举每一个深度指定的节点

a

，令其在原状态中的父亲为

f

，那么只要找到一个最大的节点

b

满足

b

在目标状态中的父亲与

w_f

相等（这样可以保证

a,b

现在有同一个父亲）且

c_{a,b}

为真，若最终

a\ne b

就合并

a,b

。

放代码：

CPP

/*
ID: CrowMatrix
TASK: Tree Merging
LANG: C++
*/
#include<bits/stdc++.h>
using namespace std;
int p1[1001],p2[1001],d[1001],w[1001];
bool e[1001],c[1001][1001];
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,r; cin>>n;
    for(int i=1;i<=n;i++)p1[i]=p2[i]=e[i]=w[i]=d[i]=0;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)c[i][j]=false;
    for(int i=1;i<n;i++){
      int v,p; cin>>v>>p; p1[v]=p;
    } // 原状态
    for(int i=1;i<=n;i++)if(!p1[i])r=i;
    int m; cin>>m; e[r]=true;
    for(int i=1;i<m;i++){
      int v,p; cin>>v>>p; p2[v]=p,e[v]=true;
    } // 目标状态
    for(int i=n;i;i--)
      for(int j=1;j<=n;j++)
        if(j!=r)d[j]=d[p1[j]]+1; // 计算节点深度
    for(int i=n;i;i--)
      for(int j=1;j<=n;j++)
        if(d[j]==i)
          if(e[j])c[j][j]=true;
          else for(int k=j;k<=n;k++)
            if(e[k])for(int l=c[j][k]=1;l<=n;l++)
              if(p1[l]==j){
                bool f=false;
                for(int p=1;p<=n;p++)
                  f|=p2[p]==k&&c[l][p];
                c[j][k]&=f; // 逐一检查各项条件是否满足
              }
    cout<<n-m<<endl; w[r]=r;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        if(d[j]==i){
          for(int k=1;k<=n;k++)
            if(p2[k]==w[p1[j]]&&c[j][k])w[j]=k; // 找合并的目标
          if(j!=w[j])cout<<j<<' '<<w[j]<<endl;
        }
  }
  return 0;
}

[USACO23OPEN] Tree Merging G 题解

文章操作

前言

解法

相关推荐

评论

[USACO23OPEN] Tree Merging G 题解