ZR #1190. 【線上訓練 15】生成樹

#include <bits/stdc++.h>
#define

using namespace std;
typedef long long ll;
int n; ll g[A][A], siz[1 << A];
ll coms[1 << A][A], sizt[1 << A];
ll f[1 << A][A], w[A];

int main(int argc, char const *argv[]) {
  cin >> n;
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++)
      scanf("%d", &g[i][j]), g[j][i] = g[i][j];
  for (int i = 1; i < 1 << n; i++)
    for (int j = 1; j <= n; j++)
      if (!(i & (1 << (j - 1)))) coms[i][++sizt[i]] = j; //i集合的補集; sizt[i]是補集大小
  for (int i = 1; i <= n; i++) w[i] = 1LL * i * (n - i); //w[i]是二進制下有i個1時任意一條邊的貢獻次數，與點的個數有關
  memset(f, 0x3f, sizeof f);
  for (int i = 1; i <= n; i++) f[1 << (i - 1)][i] = 0;
  for (int i = 1; i < 1 << n; i++) siz[i] = siz[i >> 1] + (i & 1); //i有多少位1
  for (int s = 1; s < 1 << n; s++) //目前點的集合
    for (int i = 1; i <= n; i++)
      if (s & (1 << (i - 1))) { //這個點是否在集合内
        int s1 = s ^ (1 << (i - 1)); //枚舉s的真子集
        for (int t = s1 & (s1 - 1); t; t = (t - 1) & s1) //讓f也包括補集的最優情況以減少一層補集的枚舉
          f[s][i] = min(f[s][i], f[(s1 ^ t) | (1 << (i - 1))][i] + f[t | (1 << (i - 1))][i]);
        for (int j = 1; j <= n; j++) if (!(s & (1 << (j - 1)))) //可轉移到其他點
          f[s | (1 << (j - 1))][j] = min(f[s | (1 << (j - 1))][j], f[s][i] + g[i][j] * w[siz[s]]);
        // for (int s1 = (s - 1) & s; s1; s1 = (s1 - 1) & s) //枚舉s的子集s1
        //  if ((s1 & (1 << i - 1))) //目前點也在s的子集s1中
        //    for (int j = 1; j <= sizt[s1]; j++) { //枚舉不在s1中的點（枚舉s1補集中的點）
        //      int t = siz[s ^ s1], l = coms[s1][j]; //s^s1就是s1對s的補集，l是該點
        //      f[s][i] = min(f[s][i], f[s ^ s1][l] + f[s1][i] + g[i][l] * w[t]);
        //    }
      }
  ll ans = 1e18;
  for (int i = 1; i <= n; i++) ans = min(ans, f[(1 << n) - 1][i]);
  cout << ans << endl;
}