D-Armchairs 最小費用流で辺の張り方を工夫 (交差しない二部マッチング)

• Quiz
  • https://codeforces.com/contest/1525/problem/D
• AC
  • https://codeforces.com/contest/1525/submission/116394091
  • 327ms...
• 想定解
  • DP
• 別解の最小費用流
  • 辺を張りすぎてコンテスト中はTLE止まり
  • れたすさんが辺の張り方を工夫して通した
  • その方法は以下の画像の右下の通り(capacity = inf, cost = 1)
• 計算量
  • ACLによるとフローをFとしてF(N+M)log(N+M) https://atcoder.github.io/ac-library/production/document_ja/mincostflow.html
  • N=5000, 最初の2500個に着席している場合はF(移動距離)=2500x2500なのでTLEする気がする... (間違っていたら教えてほしい)
• 学び
  • 辺が多すぎてフローできない時は、超頂点、または辺の張り方の工夫

#include <atcoder/mincostflow>
using namespace atcoder; // 忘れがち

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

    // input
    ll N;
    cin>>N;

    VI A(N);
    rep(i, N) cin >> A[i];

    VI O,Z;
    rep(i,N){
      if(A[i]==0){
        Z.push_back(i);
      }else{
        O.push_back(i);
      }
    } 

    ll start=N;
    ll goal=N+1;
    mcf_graph<int, long long> g(N+2);

    for(ll o : O){
      g.add_edge(start,o,1,0);
    }
    
    // 愚直に1から0へ辺を張る。絶対に不要な辺を削ってもTLE...
    // ll diff = SZ(Z)-SZ(O);
    // rep(i,SZ(O)){
    //   FOR(j,i,SZ(Z)){
    //     if(j-i>diff)break;
    //     g.add_edge(O[i],Z[j],1,abs(O[i]-Z[j]));
    //   }
    // }

    // こうすると辺の数がO(N)になる！
    rep(i,N-1){
      g.add_edge(i,i+1,1e9,1); // ここのコスト1がabs(A[i]-A[j])に対応している！
      g.add_edge(i+1,i,1e9,1);
    }

    for(ll z : Z){
      g.add_edge(z,goal,1,0);
    }
    auto result = g.flow(start,goal,SZ(O));
    ll cost = result.second;
    p(cost);

    return 0;
}