CF1906I Contingency Plan 2 题解

· · 题解

被大佬 @未来姚班zyl 一眼秒了。

有结论：一个 DAG 的拓扑序确定的充要条件为它具有一个生成子图^{[1]}是一条长度为 n 的链。于是现在的问题就变成了如何加最少的边构造出这样的链。

注 [1]：一个图 G=(V,E) 的一个生成子图 G'=(V',E') 是一个满足 V'=V\land E'\subseteq E 的图。也就是说，生成子图是原图中保留所有结点、并删去若干条边（可以不删）形成的子图。

解决上面的问题可以考虑经典的最小路径覆盖问题，因为显然我们需要找出若干条点不相交的路径，并将它们首尾相接形成一条长度为 n 的链——需要加的边数就是路径数减 1 的值。这个东西可以用匈牙利算法跑，朴素的跑不过去（会 TLE on Test #7）；但是众所周知的匈牙利常数已经极其小了，加入一些技巧直接让 n=10^5 跑进 200\mathrm{ms}。

现在还有一个问题，就是找出路径之后，不能使用随便的顺序将它们连在一起——因为原图是一个有向树，这么做可能会成环。解决这个问题的方法是简单的，只需要将所有路径缩成一个点后在原图上跑出拓扑序，按照拓扑序从小到大将路径排序，之后依次相连即可保证不出现环。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
inline vector<vector<int> > cover(int n,vector<pii> e){
  vector<vector<int> > g(n<<1);
  for(auto [u,v]:e)
    g[u+n].emplace_back(v);
  vector<int> b(n<<1,-1),v(n),p(n<<1,-1);
  function<bool(int,int)> dfs=[&](int u,int t){
    for(int i:g[u])
      if(b[i]<t)
        if(b[i]=t;p[i]<0||dfs(p[i],t))
          return p[i]=u,p[u]=i,true;
    return false;
  }; // 匈牙利算法
  iota(v.begin(),v.end(),n);
  shuffle(v.begin(),v.end(),mt19937(time(0)));
  int t=0;
  for(int i:v)dfs(i,t++);
  vector<vector<int> > r;
  for(int i=0;i<n;i++)
    if(p[i]<0){
      int u=i; vector<int> v={u};
      while(~p[u+n])v.emplace_back(u=p[u+n]);
      r.emplace_back(v);
    }
  return r;
} // 最小路径覆盖
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,c=0; cin>>n;
  vector<pii> e(n-1);
  for(auto &[u,v]:e)cin>>u>>v,u--,v--;
  auto r=cover(n,e);
  vector<int> id(n);
  for(int i=0;i<r.size();i++)
    for(int j:r[i])id[j]=i; // 缩点
  vector<vector<int> > g(r.size());
  vector<int> d(r.size()),o(r.size()),p(r.size());
  for(auto [u,v]:e)
    if(id[u]!=id[v])g[id[u]].emplace_back(id[v]),d[id[v]]++;
  queue<int> q;
  for(int i=0;i<r.size();i++)
    if(!d[i])q.emplace(i);
  while(!q.empty()){
    int u=q.front(); o[u]=c++,q.pop();
    for(int i:g[u])
      if(!--d[i])q.emplace(i);
  } // 跑出拓扑序
  iota(p.begin(),p.end(),0);
  sort(p.begin(),p.end(),[&](int x,int y){
    return o[x]<o[y];
  });
  cout<<r.size()-1<<endl;
  for(int i=1;i<p.size();i++)
    cout<<r[p[i-1]].back()+1<<' '<<r[p[i]][0]+1<<'\n';
  return 0;
}