题目链接

LOJ3210

题目描述

给定一棵树,树上的每一个节点都有一个数字$[1,n]$,互不相同。

每次删去一条边,交换边两个节点上的数字。

最后的方案是按照数字从小到大输出当前的所在节点的编号。

请你输出字典序最小的方案,最后的状态。

数据范围:$n\leq 2000$

思路要点

子任务 菊花图

模拟后发现,按照某种顺序删边后,所有的边会按照其删去的顺序构成一个偏序链

一个合法的方案就是满足在非结束时刻不构成任意一个有始有终的偏序链,具体地说就是不存在任意一个时刻,已经存在了一个有始有终的偏序链,但是还有其他的边不在链内

防止构成这种情况,我们用并查集维护当前中心节点的所有边的连通性。

#include <bits/stdc++.h>
#define For(i,s,t) for(int i=s;i<=t;i++)

using namespace std;

const int N = 2e3 + 5;

int n;
int fa[N], bk[N], a[N], vis[N], ans[N], dg[N], p[N];
pair<int, int> edge[N];

int main() {
  freopen("tree.in", "r", stdin); 
  freopen("tree.out", "w", stdout);
  
#ifdef ONLINE_JUDGE
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
#endif
  
  int t;
  cin >> t;
  
  function<int(int)> getFa;
  getFa = [&](int x) {
    return fa[x] == x ? x : fa[x] = getFa(fa[x]);
  };
  
  while (t--) {
    cin >> n;
    For (i, 1, n) {
      cin >> bk[i];
      a[bk[i]] = i, dg[i] = ans[i] = 0;
    }
    For (i, 1, n - 1) {
      cin >> edge[i].first >> edge[i].second;
      dg[edge[i].first]++, dg[edge[i].second]++;
    }
    bool isjh = 0;
    For (i, 1, n) {
      if (dg[i] == n - 1) {
        isjh = 1;
      }
    }
    
    function<void()> caseForjh = [&]() {
      For (i, 1, n) {
        fa[i] = i, vis[i] = 0;
      }
      For (i, 1, n) {
        For (j, 1, n) {
          if (!vis[j] && (i == n || getFa(bk[i]) != getFa(j))) {
            fa[bk[i]] = getFa(j);
            ans[i] = j;
            vis[j] = 1;
            break;
          }
        }
      }
      For (i, 1, n) {
        cout << ans[i] << ' ';
      }
      cout << '\n';
    };
    
    if (isjh) {
      caseForjh();
      continue;
    }
    
    function<void()> bruteForce = [&]() {
      For (i, 1, n - 1) {
        p[i] = i;
      }
      vector<int> tmp(n + 1);
      tmp.clear();
      do {
        For (i, 1, n) {
          tmp[i] = a[i];
        }
        For (i, 1, n - 1) {
          swap(tmp[edge[p[i]].first], tmp[edge[p[i]].second]);
        }
        vector<int> goal(n + 1);
        For (i, 1, n) {
          goal[tmp[i]] = i;
        }
                
        function<int(vector<int>)> check = [&](vector<int> t) {
          if (ans[1] == 0) {
            return 1;
          }
          For (i, 1, n) {
            if (ans[i] != t[i]) {
              return (int)(ans[i] > t[i]);
            }
          }
          return 0;
        };
        
        if (check(goal)) {
          For (i, 1, n) {
            ans[i] = goal[i];
          }
        }
      } while (next_permutation(p + 1, p + n));
      For (i, 1, n) {
        cout << ans[i] << ' ';
      }
      cout << '\n';
    };
    
    if (n <= 10) {
      bruteForce();
      continue;
    }
  }
  return 0; 
}

子任务 链

每一个节点的度数最多是$2$,也就是说对于所有节点的边只有存在三种情况,先删左边再删右边,先删右边再删左边,还没被确定状态。

直接大力贪心就可以了。

#include <bits/stdc++.h>
#define For(i,s,t) for(int i=s;i<=t;i++)

using namespace std;

const int N = 2e3 + 5;

int pt[N], a[N], dg[N], id[N], vis[N], ans[N];
int tag[N]; 
/**
 * tag = 0, none
 * tag = 1, first left then right
 * tag = 2, first right then left
 */ 
int n, cnt;
vector<int> g[N];

int main() {
  freopen("tree.in", "r", stdin);
  freopen("tree.out", "w", stdout);
#ifdef ONLINE_JUDGE
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
#endif
  int t;
  cin >> t;
  while (t--) {
    
    auto init = [&]() {
      For (i, 1, n) {
        g[i].clear();
        dg[i] = id[i] = tag[i] = vis[i] = 0;
      }
      cnt = 0;
    };
    
    cin >> n;
    init();
    For (i, 1, n) {
      cin >> pt[i];
      a[pt[i]] = i;
    }
    For (i, 1, n - 1) {
      int u, v;
      cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
      dg[u]++, dg[v]++;
    }
    For (i, 1, n) {
      if (dg[i] == 1) {
        
        function<void(int, int)> dfs;
        dfs = [&](int u, int pre) {
          id[u] = ++cnt;
          for (auto v : g[u]) {
            if (v != pre) {
              dfs(v, u);
            }
          }
        };
        
        dfs(i, 0);
        break;
      }
    }
    For (i, 1, n) {
      int obj = pt[i];
      For (j, 1, n) {
        // try to finish the tour from obj->j
        
        function<bool(int, int)> check = [&](int u, int v) { // from u->v
          if (id[u] < id[v]) {
            if (tag[id[u]] == 1 || tag[id[v]] == 1) {
              return 0;
            }
            For (i, id[u] + 1, id[v] - 1) {
              if (tag[i] == 2) {
                return 0;
              } 
            }
            return 1;
          } else { 
            if (tag[id[u]] == 2 || tag[id[v]] == 2) {
              return 0;
            }
            For (i, id[v] + 1, id[u] - 1) {
              if (tag[i] == 1) {
                return 0;
              } 
            }
            return 1;
          }
        };
          
        function<void(int, int)> update = [&](int u, int v) { // from u->v
          if (id[u] < id[v]) {
            if (id[u] != 1) {
              tag[id[u]] = 2;
            }
            if (id[v] != n) {
              tag[id[v]] = 2;
            }
            For (i, id[u] + 1, id[v] - 1) {
              tag[i] = 1;
            }
          } else {
            if (id[u] != n) {
              tag[id[u]] = 1;
            }
            if (id[v] != 1) {
              tag[id[v]] = 1;
            }
            For (i, id[v] + 1, id[u] - 1) {
              tag[i] = 2;
            }
          }
        };
        
        if (!vis[j] && check(obj, j) && obj != j) {
          update(obj, j);
          ans[i] = j; 
          vis[j] = 1;
          break;
        }
      }
    }
    For (i, 1, n) {
      cout << ans[i] << ' ';
    }
    cout << '\n';
  }
  return 0; 
}

正解

首先每个点删边的顺序的独立的,所以只需要考虑每一个点内的删边的顺序。

将每个点的所有边都看做一个点,构建新图,考虑从$u\rightarrow v$的合法路径满足的条件

考虑结合子任务一和子任务二的思路。

首先对于一条合法的从$u\rightarrow v$的路径,成立的充要条件为$u\rightarrow v$的路径的第一条路径必须是$u$上第一条被删去的边,中间的路径必须是连续删去,最后一条必须是$v$中最后一个被删去的路径,否则这个数一定会被运到其他的节点。

对于新图,一个新的节点的出边和入边就代表的两条边被删去的顺序。

我们直接考虑扩展合法的答案,$(pre,u,ed,v)$表示$u$的入边为$pre$,出边为$ed$,下一个节点为$v$。

如果$u$能做终点的条件是,$u$不能为起点而且不能存在最后一条删的边或者满足最后一条删去的边为$pre$,对于$pre$必须满足$pre$不存在出边,也不能存在有始有终的偏序链。

对于中间的节点,必须满足$pre$和$ed$分别不存在出边和入边,或者存在第一条被删去的边,不能和$pre$构成偏序链,或者存在最后一条被删的边,不能和$ed$构成偏序链。

对于起点必须满足$u$不存在第一条被删去的边或者第一条被删去的边为$pre$,或者可以和$ed$构成偏序链。

这样我们就可以用$O(n)$的时间找出答案,然后就是更新新图。

如果用并查集维护偏序链,那么复杂度为 $O(n^2\alpha(n))$,也可以用链表维护,时间复杂度为 $O(n^2)$

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define For(i, s, t) for (int i = s; i <= t; i++)

using namespace std;

const int N = 2005;

template <class T> 
void chkMax(T& x, T y) {
  x = x > y ? x : y;
}

template <class T> 
void chkMin(T& x, T y) {
  x = x < y ? x : y;
}

struct Edge {
  int to, nt;
} E[N << 1];

struct List {
  int fa[N];
  bool hvi[N], hvo[N];
  
  void init(int n) {
    For (i, 1, n) {
      fa[i] = i;
      hvi[i] = hvo[i] = 0;
    }
  }
  
  int get(int x) {
    return fa[x] == x ? x : fa[x] = get(fa[x]);
  }
  
  bool check(int x, int y) {
    return get(x) == get(y);
  }
  
  void merge(int u, int v) {
    int a = get(u), b = get(v);
    if (a != b) {
      fa[a] = b;
    }
  }
} lt[N];

int H[N], pt[N], dg[N], lst[N], fst[N];
int n, edgeCnt;

int main() {
  freopen("tree.in", "r", stdin);
  freopen("tree.out", "w", stdout);
#ifdef ONLINE_JUDGE
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
#endif
  int t;
  cin >> t;
  while (t--) {
    cin >> n;
    
    auto init = []() {
      edgeCnt = 1;
      memset(H, 0, sizeof H);
      For (i, 1, n) {
        lt[i].init(n);
        fst[i] = lst[i] = dg[i] = 0;
      }
    };
    
    init();
    For (i, 1, n) {
      cin >> pt[i];
    }
    For (i, 1, n - 1) {
      int u, v;
      cin >> u >> v;
      
      function<void(int, int)> add = [&](int u, int v) {
        E[++edgeCnt] = (Edge){v, H[u]};
        H[u] = edgeCnt;
        dg[v]++;
      };
      
      add(u, v);
      add(v, u);
    }
    For (i, 1, n) {
      
      function<int(int, int)> find;
      find = [&](int u, int pre) { // pre : id of prefix edge(income) 
        int res = inf;
        if (pre) {
          if (!lst[u] || lst[u] == pre) {
            if (!lt[u].hvo[pre] && !(dg[u] > 1 && fst[u] && lt[u].check(pre, fst[u]))) {
              res = u;
            }
          }
        }
        for (int e = H[u]; e; e = E[e].nt) {
          int v = E[e].to, ed = e >> 1;
          if (ed == pre) {
            continue;
          }
          if (!pre) {
            if (!fst[u] || fst[u] == ed) {
              if (!lt[u].hvi[ed] && !(dg[u] > 1 && lst[u] && lt[u].check(lst[u], ed))) {
                chkMin(res, find(v, ed));
              }
            }
          } else {
            if (pre != lst[u] && ed != fst[u] && !lt[u].check(pre, ed)) {
              if (!lt[u].hvo[pre] && !lt[u].hvi[ed]) {
                if (!(dg[u] > 2 && fst[u] && lst[u] && lt[u].check(fst[u], pre) && lt[u].check(lst[u], ed))) {
                  chkMin(res, find(v, ed));
                }
              }
            }
          }
        }
        return res;
      };
      
      function<bool(int, int, int)> update;
      update = [&](int u, int pre, int gol) {
        if (u == gol) {
          lst[u] = pre;
          return 1;
        }
        for (int e = H[u]; e; e = E[e].nt) {
          int v = E[e].to, ed = e >> 1;
          if (ed == pre) {
            continue;
          }
          if (update(v, ed, gol)) {
            if (!pre) {
              fst[u] = ed;
            } else {
              lt[u].hvo[pre] = lt[u].hvi[ed] = 1;
              lt[u].merge(ed, pre);
              dg[u]--;
            }
            return 1;
          }
        }
        return 0;
      };
      int gl = find(pt[i], 0);
      update(pt[i], 0, gl);
      cout << gl << ' ';
    }
    cout << '\n';
  }
  return 0; 
}
最后修改:2020 年 03 月 18 日 09 : 18 AM
如果觉得我的文章对你有用,请随意赞赏