中国人郵便配達問題 Chinese Postman Problem (CPP) bitDP ~全ての辺を1度は通って始点に戻る~

ライブラリ

f:id:peroon:20200930101528p:plain

中国人郵便配達問題とは？：Gを連結な無向グラフとし、Gの各辺には距離が割り当てられている。このとき、Gの辺をすべて通るような閉路のうち、距離の合計が最小になるものを求めよ（※同じ辺を複数回通ってもよい）

// 完全グラフ上の最小マッチング
// G : graph
// D : distance
// ※頂点数は偶数を仮定
ll minimum_matching_of_perfect_graph(VV& G, VV& D){
  ll N = SZ(G);
  assert(N%2==0);
  assert(SZ(G)==SZ(D));
  
  // dp[flag]
  VI dp(1<<N, inf);
  dp[0]=0;

  rep(f, 1<<N){
    // 現在のフラグから遷移できる箇所へ遷移する
    rep(i,N){
      FOR(j,i+1,N){
        if((f>>i&1)==0 && (f>>j&1)==0){
          // その2箇所を選ぶ
          ll d = D[i][j];
          ll new_flag = f | (1<<i) | (1<<j);
          chmin(dp[new_flag], dp[f] + d);
        }  
      }
    }
  }
  return dp[(1<<N)-1];
}

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

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

    VI S(M);
    VI T(M);
    VI D(M);
    rep(i,M) cin>>S[i]>>T[i]>>D[i];

    auto wa = WarshallFloyd(N);

    VV G(N);
    rep(i,M){
      ll s = S[i];
      ll t = T[i];
      ll d = D[i];

      G[s].push_back(t);
      G[t].push_back(s);

      wa.register_edge2(s,t,d);
    }
    wa.calc();

    // 次数が奇数のものだけで完全グラフを作る
    {
      VI A;
      rep(i,N){
        if(SZ(G[i])%2==1){
          A.push_back(i);
        }
      }
      ll n = SZ(A);

      VV F(n); //完全グラフ
      VV H(n, VI(n, inf)); // 距離行列

      rep(i,n){
        FOR(j,i+1,n){
          ll a = A[i];
          ll b = A[j];
          F[i].push_back(j);
          F[j].push_back(i);

          ll d = wa.distance(a,b);
          H[i][j]=d;
          H[j][i]=d;
        }
      }

      ll v = minimum_matching_of_perfect_graph(F, H);
      ll ans = SUM(D) + v;
      p(ans);
    }

    return 0;
}

関連：TSP