P9542 [湖北省选模拟 2023] 棋圣 / alphago

Alex_Wei · 2023-08-22 15:34:25 · 题解

*P9542 [湖北省选模拟 2023] 棋圣 / alphago

很牛的题目啊。

先考虑一棵树怎么做：操作不改变棋子任意两个棋子之间的距离的奇偶性将整棵树黑白染色后，只有所在位置颜色不同，且棋子本身颜色不同的棋子对可能产生贡献。设 c_{i, j} 表示所在位置颜色为 i，棋子本身颜色为 j 的棋子数量，那么答案有显然的上界：(c_{0, 0} c_{1, 1} + c_{0, 1} c_{1, 0}) \max w。

考虑何时能取到上界，这要求我们将所有所在位置颜色不同的棋子全部堆到同一个点上。可以这样理解操作：让棋子之间变得越来越密集，每次操作不增加棋子之间的距离。当所有棋子形成一个连通块时，接下来无论如何操作，所有棋子仍然是一个连通块。因此，考虑接下来一步操作，若存在某对棋子之间的距离减少了，那么操作点和这两颗棋子一定不在一条链上。这说明存在度数大于 2 的点是可以取到上界的必要条件。

那么它充分吗？考虑某个度数大于 2 的点的任意三棵子树内的任意叶子 x, y, z。第一步任意操作，然后重复操作 x, y, z。容易证明在足够多次操作后，任意一对棋子之间的距离不大于 1。因此，存在度数大于 2 的点是答案可以直接取到上界的充要条件。

没有度数大于 2 的点时，整张图是一条链，相邻两枚棋子之间的距离不增，非负，且奇偶性不变。满足条件的状态都是可达的，因为一次操作相当于将某对相邻棋子之间的距离减少 2，或者将所有棋子在链上平移。

设 f_{i, l, r} 表示第 i 个点有第 [l, r] 枚棋子的最大权值。转移枚举下一个有棋子的位置 j，和新的右边界 r'。因为 j - i 不大于第 r 枚棋子和第 r + 1 枚棋子之间的距离，所以 i, r, j 的总数为 \mathcal{O}(n ^ 2)。时间复杂度 \mathcal{O}(n ^ 4)，常数较小。

注意到若两枚棋子距离为偶数，则它们之间不产生贡献，此时不需要记录 l。设 d_i 表示是最大的 j\geq i 满足第 i 枚棋子与第 [i + 1, j] 枚棋子的距离为偶数。如果第 p 枚棋子和之后的棋子产生贡献，那么它所在的点一定放置了第 [p, d_p] 枚棋子。从这个角度，考虑优化状态设计。设 f_{i, type, p} 表示类型为 type 的最大权值，其中：

对于 type = 0：

如果它转移到 type' = 0，那么枚举新的位置 j' 以及 p'。
如果它转移到 type' = 1，那么枚举新的位置 j'，p' 只能等于 p + 1。

对于 type = 1：新的位置 j' 只能等于 j + 1，且需要根据实际含义计算产生的贡献。

如果它转移到 type' = 0，那么枚举 p'。
如果它转移到 type' = 1，那么 p' = p + 1。

时间复杂度 \mathcal{O}(n ^ 3)。

对于有度数大于 2 的点的非链简单无向图：

如果图是二分图，那么和树的情况是类似的，所有距离为奇数的黑白棋子对产生最大边权的贡献。
如果图不是二分图，那么可以通过奇环改变任意棋子对的奇偶性：任选一棵生成树，将处于黑点的白棋通过奇环移动至白点，将处于白点的黑棋通过奇环移动至黑点，所有黑白棋子对产生最大边权的贡献。

最后考虑没有度数大于 2 的点的非链简单无向图，即简单环：因为一个点有两个方向可以选择，所以情况和有度数大于 2 的点是类似的。分成偶环和奇环讨论，用有度数大于 2 的点的非链简单无向图做法即可。时间复杂度 \mathcal{O}(n + m)。

综上，我们将问题分成三种情况：链，非链二分图和非链非二分图。

总时间复杂度 \mathcal{O}(n ^ 3)。

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

bool Mbe;
constexpr int N = 100 + 5;

int n, m, k, bipar;
int ch[N], col[N];
vector<pii> e[N];

void dfs(int id, int c) {
  col[id] = c, c ^= 1;
  for(pii _ : e[id]) {
    int it = _.first;
    if(col[it] == -1) dfs(it, c);
    else bipar &= col[it] == c;
  }
}

/*
namespace CHAIN {
  int f[N][N][N], id[N], w[N];
  struct chess {
    int pos, col;
  } c[N];
  int c0[N], c1[N];
  void solve() {
    int cur = 0;
    for(int i = 1; i <= n; i++) {
      if(e[i].size() == 1) cur = i;
    }
    int lst = -1, cnt = 0;
    while(1) {
      id[++cnt] = cur;
      bool found = 0;
      for(pii _ : e[cur]) {
        int it = _.first;
        if(it != lst) {
          w[cnt] = _.second;
          lst = cur, cur = it;
          found = 1;
          break;
        }
      }
      if(!found) break;
    }
    cnt = 0;
    for(int i = 1; i <= n; i++) {
      if(ch[id[i]] != -1) c[++cnt] = {i, ch[id[i]]};
    }
    for(int i = 1; i <= cnt; i++) {
      c0[i] = c0[i - 1] + (c[i].col == 0);
      c1[i] = c1[i - 1] + (c[i].col == 1);
    }
    memset(f, 0xcf, sizeof(f));
    f[0][0][0] = 0;
    for(int i = 0; i < n; i++) {
      for(int l = 0; l < cnt; l++) {
        for(int r = l; r < cnt; r++) {
          if(f[i][l][r] < 0) continue;
          int dis = c[r + 1].pos - c[r].pos, lim = r ? min(n, i + dis) : n;
          for(int j = i + (!i || (dis & 1) ? 1 : 2); j <= lim; j += (i ? 2 : 1)) {
            for(int nr = r + 1; nr <= cnt; nr++) {
              int val = f[i][l][r];
              if(j == i + 1 && r) {
                int coef = (c0[r] - c0[l - 1]) * (c1[nr] - c1[r]);
                coef += (c1[r] - c1[l - 1]) * (c0[nr] - c0[r]);
                val += coef * w[i];
              }
              f[j][r + 1][nr] = max(f[j][r + 1][nr], val);
              if(nr < cnt && (c[nr + 1].pos - c[nr].pos & 1)) break;
            }
          }
        }
      }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
      for(int l = 1; l <= cnt; l++) {
        ans = max(ans, f[i][l][cnt]);
      }
    }
    cout << ans << "\n";
  }
}
*/

namespace CHAIN {
  int f[N][2][N], id[N], w[N], nxt[N];
  struct chess {
    int pos, col;
  } c[N];
  int c0[N], c1[N];
  void solve() {
    int cur = 0;
    for(int i = 1; i <= n; i++) {
      if(e[i].size() == 1) cur = i;
    }
    int lst = -1, cnt = 0;
    while(1) {
      id[++cnt] = cur;
      bool found = 0;
      for(pii _ : e[cur]) {
        int it = _.first;
        if(it != lst) {
          w[cnt] = _.second;
          lst = cur, cur = it;
          found = 1;
          break;
        }
      }
      if(!found) break;
    }
    cnt = 0;
    for(int i = 1; i <= n; i++) {
      if(ch[id[i]] != -1) c[++cnt] = {i, ch[id[i]]};
    }
    for(int i = cnt; i; i--) {
      nxt[i] = i;
      if(i < cnt && (c[i + 1].pos - c[i].pos & 1 ^ 1)) nxt[i] = nxt[i + 1];
    }
    for(int i = 1; i <= cnt; i++) {
      c0[i] = c0[i - 1] + (c[i].col == 0);
      c1[i] = c1[i - 1] + (c[i].col == 1);
    }
    memset(f, 0xcf, sizeof(f));
    f[0][0][0] = 0;
    for(int i = 0; i < n; i++) {
      for(int tp : {0, 1}) {
        for(int p = 0; p < cnt; p++) {
          if(f[i][tp][p] < 0) continue;
          int dis = c[(tp ? nxt[p] : p) + 1].pos - c[tp ? nxt[p] : p].pos;
          int lim = i ? min(n, i + dis) : n;
          for(int j = i + (!i || (dis & 1) ? 1 : 2); j <= lim; j += (i ? 2 : 1)) {
            if(tp == 0) {
              // 0 -> 0
              for(int q = p + 1; q <= nxt[p + 1]; q++) {
                f[j][0][q] = max(f[j][0][q], f[i][tp][p]);
              }
              // 0 -> 1
              f[j][1][p + 1] = max(f[j][1][p + 1], f[i][tp][p]);
            }
            else if(j == i + 1 && nxt[p] < cnt) {
              // 1 -> 0
              int l = nxt[p] + 1, r = nxt[l];
              for(int q = l; q <= r; q++) {
                int coef = (c0[nxt[p]] - c0[p - 1]) * (c1[q] - c1[nxt[p]]);
                coef += (c1[nxt[p]] - c1[p - 1]) * (c0[q] - c0[nxt[p]]);
                f[j][0][q] = max(f[j][0][q], f[i][tp][p] + coef * w[i]);
              }
              // 1 -> 1
              int coef = (c0[nxt[p]] - c0[p - 1]) * (c1[r] - c1[l - 1]);
              coef += (c1[nxt[p]] - c1[p - 1]) * (c0[r] - c0[l - 1]);
              f[j][1][l] = max(f[j][1][l], f[i][tp][p] + coef * w[i]);
            }
          }
        }
      }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) ans = max(ans, f[i][0][cnt]);
    cout << ans << "\n";
  }
}

bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE *IN = freopen("alphago.in", "r", stdin);
    FILE *OUT = freopen("alphago.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> n >> m >> k;
  memset(ch, -1, sizeof(ch));
  for(int i = 1; i <= k; i++) {
    int x, c;
    cin >> x >> c;
    ch[x] = c;
  }
  int maxw = 0;
  for(int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    e[u].push_back({v, w});
    e[v].push_back({u, w});
    maxw = max(maxw, w);
  }

  bool chain = 0;
  for(int i = 1; i <= n; i++) chain |= e[i].size() == 1;
  for(int i = 1; i <= n; i++) chain &= e[i].size() <= 2;
  if(chain) CHAIN::solve(), exit(0);

  memset(col, -1, sizeof(col));
  bipar = 1, dfs(1, 0);
  if(bipar) {
    vector<vector<int>> c(2, vector<int>(2));
    for(int i = 1; i <= n; i++) {
      if(ch[i] != -1) c[ch[i]][col[i]]++;
    }
    cout << maxw * (c[0][0] * c[1][1] + c[0][1] * c[1][0]) << "\n";
  }
  else {
    vector<int> c(2);
    for(int i = 1; i <= n; i++) {
      if(ch[i] != -1) c[ch[i]]++;
    }
    cout << maxw * (c[0] * c[1]) << "\n";
  }

  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}

/*
g++ alphago.cpp -o alphago -O2 -std=c++14 -DALEX_WEI
*/