[COCI 2025/2026 #3] 宴会 / Domjenak 题解

FFTotoro · 2025-12-17 23:07:51 · 题解

题目说了完美匹配唯一，根据这个题的结论，这种情况必然存在一度点，并且通过类似拓扑排序、不断删一度点的方式就可以找出完美匹配。记这个完美匹配为 \{(p_1,q_1),(p_2,q_2),\ldots,(p_N,q_N)\}。

考察最终答案的形态——最终输出的那个路径形如 p_{a_1},q_{a_1},p_{a_2},q_{a_2},\ldots,p_{a_{K/2}},q_{a_{K/2}}。我们要找到最大的 K 和一个这样的序列。观察到从 p_i“进去”，接着都必须要从 q_i“出去”，这个问题有一种很智慧的处理方法，就是建图的时候是双向边，现在对于所有 i 把 p_i,q_i 的出边互换，入边不变，建出一张新图，就完美地解决了这个问题（经过 p_i 就相当于走过一条边 p_i\to q_i，反之亦然）。

现在问题转换成了有向图最长链。可以发现这是个 DAG，并且不会走重复的点（意思就是不会先走 p_i\to q_i，再走 q_i\to p_i，即在新图上不会同时经过 p_i,q_i 两个结点），证明如下：

• 如果新图出现了环，就相当于在原图上有个环形如 p_{c_1}\to q_{c_1}\to p_{c_2}\to q_{c_2}\to\cdots\to p_{c_L}\to q_{c_L}\to p_{c_1}\to\cdots，这个时候可以把整个环上的匹配循环移位形成一种新的匹配方式，但是题目保证了完美匹配唯一，所以新图是个 DAG；
• 题目保证了原图是个二分图，黑白染色一下，一对匹配的两个点颜色不同，而上面新图的连边方式保证了一条边只会连接两个颜色相同的点，也就是说一对匹配中的点不可能在同一个弱连通分量里面，即不可能有一条路径把它们串起来。

于是就是 DAG 最长链问题。跑一遍拓扑排序做个 DP，转移时记录一下前驱以输出方案。

时间复杂度 O(n)。

放代码（当时打的现场赛，可能写得比较丑）：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,m; cin>>n>>m;
  vector<vector<int> > g(n<<1);
  for(int i=0;i<m;i++){
    int u,v; cin>>u>>v;
    g[--u].emplace_back(--v);
    g[v].emplace_back(u);
  }
  vector<bool> b(n<<1),b2(n<<1);
  vector<int> d(n<<1);
  queue<int> q;
  for(int i=0;i<n<<1;i++)
    if((d[i]=g[i].size())==1)
      b[i]=true,q.emplace(i);
  vector<pair<int,int> > v;
  while(!q.empty()){
    int u=q.front(),p=0; q.pop();
    while(p<g[u].size()&&b[g[u][p]])p++;
    if(p<g[u].size()){
      b[g[u][p]]=true;
      b2[u]=b2[g[u][p]]=true;
      v.emplace_back(u,g[u][p]);
      for(int i:g[g[u][p]])
        if(!b[i]&&--d[i]==1)
          b[i]=true,q.emplace(i);
    }
  } // 第一遍拓扑排序找匹配
  for(int i=0;i<n<<1;i++)
    if(!b2[i]){
      for(int j:g[i])
        if(!b2[j]){v.emplace_back(i,j),b2[i]=b2[j]=true; break;}
    }
  vector<int> f(n<<1),w(n<<1),pr(n<<1,-1);
  for(auto [x,y]:v)f[x]=y,f[y]=x,swap(g[x],g[y]); // 交换出边
  fill(d.begin(),d.end(),0);
  for(int i=0;i<n<<1;i++)
    for(int j:g[i])if(i!=j)d[j]++;
  for(int i=0;i<n<<1;i++)
    if(!d[i])q.emplace(i),w[i]=1;
  while(!q.empty()){
    int u=q.front(); q.pop();
    for(int i:g[u])
      if(i!=u){
        if(w[u]+1>w[i])w[i]=w[u]+1,pr[i]=u;
        if(!--d[i])q.emplace(i);
      }
  } // 第二遍拓扑排序求最长链
  int x=max_element(w.begin(),w.end())-w.begin();
  cout<<(w[x]<<1)<<'\n';
  while(~x)cout<<f[x]+1<<' '<<x+1<<' ',x=pr[x];
  cout<<endl;
  return 0;
}