K - ニワトリのお見合い / Happy Wedding! Editorial by physics0523


まず、この問題は以下の重み最大化二部マッチングの問題です。

  • 何もしなくとも、 (\(B\) の総和)+(\(D\) の総和) だけの幸福度が得られる。
  • 仲の良いニワトリのペアである(オス \(i\) 、メス \(j\) )について、この \(2\) 羽のニワトリをマッチングすると、追加で幸福度が \(A_i+C_j-B_i-D_j\) だけ得られる。(以降、この値を \(W_{i,j}\) とおく。)なお、\(W_{i,j} \le 0\) なら、この \(2\) 羽のニワトリの仲が悪いとみなして解いても結果は変わらない。
  • 求めるべきは、可能な最大の幸福度(最大重みマッチング)である。

重み最大化二部マッチングを解く方法はいくつかあります。

1. ライブラリに頼って解く方針

当たり前ですが、重み最大化二部マッチングは 重み最大化一般マッチング の一部です。2. の方針で解こうとして混乱する場合はリンク先のライブラリに頼ってしまうのも一策でしょう。(制約の面でも、今回の問題ではリンク先のライブラリがあれば十分です。)

2. 最小費用流に帰着して解く方針

こちらの方針は、重み最大化二部マッチングを最小費用流に帰着させる方針です。(最小費用流であれば、 ACL に実装されています)
重み最大化最大二部マッチングは、以下のように解くことが出来ます。

  • まず、特殊な頂点 \(S\)\(T\) 、十分大きい整数 \(X\) を用意する。
  • 全ての \(1 \le i \le P\) について、 \(S\) からオス \(i\) に向けて最大流量 \(1\) 、(流量当たり)コスト \(0\) の辺を張る。
  • 全ての仲の良いニワトリのペア(オス \(i\) 、メス \(j\) )について、オス \(i\) からメス \(j\) に向けて最大流量 \(1\) 、コスト \(X-W_{i,j}\) の辺を張る。
  • 全ての \(1 \le i \le Q\) について、メス \(i\) から \(T\) に向けて最大流量 \(1\) 、コスト \(0\) の辺を張る。
  • このように構築したグラフに対して、\(0 \le F \le\)(可能な最大流量) に対して (流量 \(F\) ,最小コスト \(C\)) を求める。このとき、流量 \(F\) に対しての最適解は \(XF-C\) となり、求める答えは全ての流量の最適解の最大値である。この操作は、 ACL の最小費用流の .slope で実現可能です。詳しくは実装例を参照して下さい。

方針 2. の実装例:

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;
 
int main(int argc, char* argv[]){
  int p,q;
  cin >> p >> q;
  vector<string> s(p);
  for(int i=0;i<p;i++){
    cin >> s[i];
  }
  vector<long long> a(p),b(p),c(q),d(q);
  for(int i=0;i<p;i++){
    cin >> a[i] >> b[i];
  }
  for(int i=0;i<q;i++){
    cin >> c[i] >> d[i];
  }
  mcf_graph<int, long long> g(p+q+2);
  int sp1=p+q,sp2=p+q+1;
  long long res=0;
  for(int i=0;i<p;i++){
    res+=b[i];
    g.add_edge(sp1,i,1,0);
  }
  for(int i=0;i<q;i++){
    res+=d[i];
    g.add_edge(p+i,sp2,1,0);
  }
  long long large=10000000000ll;
  for(int i=0;i<p;i++){
    for(int j=0;j<q;j++){
      long long bnf=(a[i]+c[j]-b[i]-d[j]);
      if(bnf<=0 || s[i][j]=='0'){continue;}
      //cerr << i << ' ' << j << '\n';
      g.add_edge(i,p+j,1,large-bnf);
    }
  }
  auto result=g.slope(sp1,sp2);
  long long fres=res;
  for(auto &nx : result){
    //cout << nx.first << ' ' << nx.second << '\n';
    fres=max(res+large*nx.first-nx.second,fres);
  }
  cout << fres << '\n';
  return 0;
}

posted:
last update: