P10179 水影若深蓝 题解

A1234467 · 2024-02-20 17:37:46 · 题解

• Step 1：简化题意

  有一棵节点数为 n 的树，给出 m 对关系，每对关系 (u, v) 表示节点 u 与节点 v 间的路径上恰好有一个其他节点，构造出这棵树或者判断无解

• Step 2：分析题目

  • 首先我们尝试画出样例所给的树，每对关系用虚线表示
  • 按照样例输出连边

  • 不难想到，对于每对关系都可以通过同时与另一个中转点建边解决

  • 注意到如果关系间发生重叠，对于第二对关系容易有以下两种方案

  • 基于简化原则，我们尽可能不引入新点，因此我们只考虑绿色虚线的方案，由此我们可以得到关系间的传递性

  • 同时显然可以发现关系间的互异性，即对于有重叠的两对关系，我们不能将其中任意点作为与该点无关的关系的中转点

  • 基于前述的两个性质，我们考虑将重复的关系染色

  • 不难发现，如果整棵树被染成了一种颜色，那么我们无法给这种颜色找到中转点，此时无解，否则将每种颜色包含的点与任意不同颜色的点建边即可

• Step 3：代码实现

  • 用并查集染色，如果只有一种颜色则判断无解，否则将第一种颜色的所有点与一个不同颜色的点建边，其他颜色的所有点与点 1 建边即可

  #include <stdio.h>
  #include <stdlib.h>
  #include <vector>
  #include <utility>
  #include <numeric>
  
  #define K01 main
  
  #ifdef ONLINE_JUDGE
  char buf[1000000], *p1, *p2;
  #define getchar() ((p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 10000000, stdin), p1 == p2)) ? 0 : *p1++)
  #endif
  
  inline int read(){
      int res = 0;
      char ch = getchar();
      while(ch < '0' || ch > '9') ch = getchar();
      while(ch >= '0' && ch <= '9') res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
      return res;
  }
  void write(int x){
      if(x > 9) write(x / 10);
      putchar(x % 10 + 48);
  }
  
  int find(std::vector<int> &set, int x){
      int &tmp = set[x];
      return tmp == x ? x : tmp = find(set, tmp);
  }
  
  int K01(){
      int T = read();
      while(T--){
          int n = read(), m = read();
          std::vector<int> vec(n + 1);
          std::iota(vec.begin() + 1, vec.end(), 1);
          for(int i = 1; i <= m; ++i){
              int u = find(vec, read()), v = find(vec, read());
              if(u > v) std::swap(u, v);
              vec[v] = u;
          }
          std::vector<int> color(n + 1);
          int flag = 0, cnt = 0;
          for(int i = 1; i <= n; ++i){
              if(vec[i] == i) color[i] = ++cnt;
              else color[i] = color[vec[i]];
              if(cnt != 1 && !flag) flag = i;
          }
          if(cnt == 1){ printf("No\n"); continue;}
          printf("Yes\n");
          for(int i = 1; i <= n; ++i){
              if(i == flag) continue;
              else if(color[i] == 1) write(i), putchar(' '), write(flag), putchar('\n');
              else putchar('1'), putchar(' '), write(i), putchar('\n');
          }
      }
      return 0;
  }

  • 上述代码 56ms 目前最优解第二

    （第一的5ms提交记录只有一个测试点不算在内）

    （目前，指 2024.2.20-17:46）

  • 加卡常头到最优解第一

    （upd:2024.2.23-11:35）