[GDKOI2024 提高组] 匹配 题解

· · 题解

很好的 Graph Matchings 题。

先考虑找出一个完美匹配，如果找不到肯定就是无解。如果这个完美匹配上黑边的数量为偶数直接输出；否则考虑使用如下的方法调整出合法的解。

考虑一个完美匹配该怎么变成另一个完美匹配；对于这个变换有个结论：改变后的边集和原来的那一部分边集并起来会形成一个环，且原边集里的边和改变后边集里的边交替出现。而我们要使更改后的黑边数量的奇偶性改变，即如果将黑边权值视为 1，白边视为 0，只需找到一个边权和为奇数且满足上述条件的环，将环内原答案内的边剔除，其他所有边加入答案。如果找不到满足条件的环，那么报告无解。

似乎题解里面很多都是网络流啊，这里供一个匈牙利算法的。找环可以借助一个栈进行 dfs。

放代码：

#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 t; cin>>t;
  while(t--){
    int n,m,k=0; cin>>n>>m;
    vector<vector<tpi> > g(n<<1),g2(n<<1);
    vector<bool> r(m),b(n<<1),c(n<<1);
    for(int i=0;i<m;i++){
      int u,v,w; cin>>u>>v>>w;
      g[--u].emplace_back(--v,w,i);
      g[v].emplace_back(u,w,i);
    }
    vector<int> p(n<<1,-1),s(n<<1);
    function<bool(int)> find=[&](int u){
      for(auto [v,w,i]:g[u])
        if(!b[v])
          if(b[v]=1;p[v]<0||find(p[v])){
            p[v]=u; return true;
          }
      return false;
    }; // 匈牙利算法找匹配
    bool f=false;
    for(int i=0;i<n&&!f;i++)
      fill(b.begin(),b.end(),0),f|=!find(i);
    if(f){cout<<"-1\n"; continue;} // 无完美匹配
    for(int u=n;u<n<<1;u++)
      for(auto [v,w,i]:g[u])
        if(p[u]==v)k+=w,r[i]=1,g2[v].emplace_back(u,w,i);
        else r[i]=0,g2[u].emplace_back(v,w,i); // 建有向边
    if(k&1){
      stack<pii> t;
      function<void(int)> dfs=[&](int u){
        b[u]=1; // 打标记
        for(auto [v,w,i]:g2[u])
          if(!f){
            if(!b[v])t.emplace(v,i),s[v]=s[u]+w,dfs(v);
            else if(c[v]&&s[u]-s[v]+w&1){
              f=true,r[i]=!r[i];
              while(!t.empty()&&t.top().first!=v)
                r[t.top().second]=!r[t.top().second],t.pop();
            } // 找到满足条件的环
          }
        if(c[u]=0;!t.empty())t.pop();
      }; // dfs 找环
      for(int i=0;i<n<<1&&!f;i++){
        fill(b.begin(),b.end(),0),fill(c.begin(),c.end(),0);
        s[i]=0,t.emplace(i,-1),c[i]=1,dfs(i);
      } // 搜索前记得清空
      if(!f){cout<<"-1\n"; continue;} // 无解
    }
    for(int i=0;i<m;i++)
      if(r[i])cout<<i+1<<' ';
    cout<<endl;
  }
  return 0;
}