最小点被覆 minimum vertex cover 2部グラフなら最大マッチングで解ける

Quiz

AC

解説

  • ワーシャルフロイドで最短距離を求め、アルファベットの条件を満たす頂点間を辺でつないだ新たなグラフGを考える
  • Gはアルファベットの条件から2部グラフ
  • 最小点被覆の位置に罠を置けばいい

その他

  • コンテスト中はvertex coverを全く考えなかったので葉の隣に罠を置いたりした
  • それだと輪っかの時に置けないので、輪っか状態なら適当に置いたりもした
  • そういうその場しのぎ的な解法では全ACは取れず

最大流ライブラリ

code

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,M,K;
    cin>>N>>M>>K;

    vector<char> C(N);
    rep(i,N)cin>>C[i];

    // edge
    VI A(M);
    VI B(M);
    rep(i,M){
      cin>>A[i]>>B[i];
      A[i]--;
      B[i]--;
    }

    WarshallFloyd wa(N);
    rep(i,M){
      wa.register_edge2(A[i],B[i],1);
    }
    wa.calc();

    // start => (a,c,e) => (b,d,f) => end
    // と流れるようにする
    MaxFlow flow(N+2);
    ll start = N;
    ll end = N+1;
    rep(i,N){
      FOR(j,i+1,N){
        if(wa.distance(i,j)<=K and next(C[i],C[j])){
          // 辺をはれる
          ll v = C[i]-'a';
          if(v%2==0){
            flow.add_edge(i, j, 1);
          }else{
            flow.add_edge(j, i, 1);
          }
        }
      }
    }
    rep(i,N){
      ll v = C[i]-'a';
      if(v%2==0){
        flow.add_edge(start, i, 1);
      }else{
        flow.add_edge(i, end, 1);
      }
    }

    ll max_flow = flow.calc(start, end);
    p(max_flow);
    
    return 0;
}