CF1939B Evidence Board 题解

· · 题解

XVIII Open Olympiad in Informatics - Final Stage, Day 1 T2 非官方题解。

唯一场切的一个；很好的树上贪心题。

题目很长、条件很多，考虑先从菊花图的部分分出发；因为所有边都有一个端点是 1，所以条件 w_{AB}\le c_A+c_B 可以转化为 w_{1B}\le c_{1,i}+c_{B,1}\Rightarrow c_{1,i}\ge w_{1B}-c_{B,1}，即给每个点安排一个对应的 c_{1,i} 使其满足这个条件。又因为不等式右边是一个定值，考虑贪心，将所有 c_{1,i} 和 w_{1B}-c_{B,1} 分别排序，如果对应位置的 c_{1,i}<w_{1B}-c_{B,1} 那么无解，否则对于每个结点 B 安排对应位置的 c_{1,i} 即可。

考虑拓展上述做法；对于一个结点 U 考虑其所有儿子：如果一个儿子 K 的所有后代都已经完成了安排，那么它必然会剩下一个 c_{K,i}（记为 up_K）上传给父亲。仍然考虑贪心，将所有从儿子传上来的 up_K 按照 w_{UK}-up_K 排序，再将自己的所有 c_{U,i} 排序，判断对应位置是否满足 c_{U,i}\ge w_{UK}-up_K。只不过这一次如果有对应位置不满足，可以将该位置的 c_{U,i} 上传给 U 的父亲，如果之后还是有不满足的就无解；如果不存在这样的 c_{U,i}，那么就把剩下来的那个最大的 c_{U,i} 上传给父亲。显然这样的策略是正确的。注意特判根结点的情况。

最后确定了每个结点的所有边的顺序后跑一遍拓扑排序就能确定全局的顺序。

代码实现有一定细节。放代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpi;
int main(){
  ios::sync_with_stdio(false);
  int n,id; cin>>n>>id;
  vector<tpi> e(n-1);
  vector<vector<tpi> > g(n);
  vector<vector<int> > c(n);
  for(int i=0;i<n-1;i++){
    auto &[u,v,w]=e[i]; cin>>u>>v>>w;
    g[--u].emplace_back(--v,w,i);
    g[v].emplace_back(u,w,i);
  }
  for(int i=0;i<n;i++){
    c[i].resize(g[i].size());
    for(auto &j:c[i])cin>>j;
  }
  for(auto &i:c)reverse(i.begin(),i.end());
  vector<vector<int> > l(n);
  for(int i=0;i<n;i++)
    l[i].resize(c[i].size(),-1);
  vector<int> up(n),ps(n);
  function<void(int,int)> dfs=[&](int u,int f){
    for(auto [i,w,n]:g[u])
      if(i!=f)dfs(i,u);
    vector<pii> s(c[u].size()),o(c[u].size());
    for(int i=0;i<c[u].size();i++)
      o[i]=make_pair(c[u][i],i);
    sort(o.begin(),o.end());
    if(u){
      int p=0,d=0;
      for(auto [i,w,n]:g[u])
        if(i!=f)s[p++]=make_pair(w-up[i],n);
        else s[c[u].size()-1]=make_pair(0,n);
      sort(s.begin(),prev(s.end()));
      for(int i=0;i<c[u].size()-1;i++){
        if(o[i+d].first<s[i].first){
          if(d)cout<<"No\n",exit(0);
          d=1,up[u]=o[i].first,ps[u]=o[i].second;
          if(o[i+d].first<s[i].first)cout<<"No\n",exit(0);
        } // 存在不满足条件的 c[u][i]
        l[u][o[i+d].second]=s[i].second;
      }
      if(!d)up[u]=o.back().first,ps[u]=o.back().second;
      l[u][ps[u]]=s.back().second;
    } // 非根结点
    else{
      for(int i=0;i<c[u].size();i++){
        auto [v,w,n]=g[u][i];
        s[i]=make_pair(w-up[v],n);
      }
      sort(s.begin(),s.end());
      for(int i=0;i<c[u].size();i++){
        if(o[i].first<s[i].first)cout<<"No\n",exit(0);
        l[u][o[i].second]=s[i].second;
      }
    } // 根结点
  };
  dfs(0,0);
  vector<vector<int> > g2(n-1);
  vector<int> d(n);
  for(int i=0;i<n;i++)
    for(int j=1;j<c[i].size();j++)
      g2[l[i][j-1]].emplace_back(l[i][j]),d[l[i][j]]++;
      // 相邻边的顺序确定
  queue<int> q;
  for(int i=0;i<n-1;i++)
    if(!d[i])q.emplace(i);
  cout<<"Yes\n";
  while(!q.empty()){
    int u=q.front(); q.pop();
    cout<<u+1<<' ';
    for(int i:g2[u])
      if(!--d[i])q.emplace(i);
  } // 拓扑排序
  return 0;
}