题解 - Codeforces 1310D Tourism

如果像我一样没有注意到二分图，也完全不会随机化，那该怎么办？

简述题意

给一图，求经过点 $1$、点数为 $k$、不含奇环、可以重复经过点和边的边权和最小环路。$n\le 80$，$k\le 10$ 且 $k$ 为偶数。

分析

我们首先考虑 meet in the middle，枚举除了点 $1$ 以外的前 $k/2-1$ 个点和后 $k/2-1$ 个点，进行搜索。最后再枚举中间三个点来合并。然后你发现会直接 TLE，如果像我一样实现常数巨大。

对两个部分分别优化：

• 对于搜索中的 TLE，发现很多边是不优的，所以选择前若干小出边 DFS，本人使用 $37$，只是因为它刚好通过了。
• 对于合并中的 TLE，发现端点处存储的答案太多了，所以对每个端点只保留前若干小方案，本人使用 $3$。

然后你发现 WA on test 129。打开发现它形如：

0 100 100 100 100...
100 0 100...

也就是说有很多同类点，导致前几小的策略容易被迷惑。

所以考虑删去同质点。对于一个点 $p$，如果存在另外至少 $2$ 个点 $q_1,q_2$，使得不考虑 $p,q$ 之间的连边，$p,q$ 向外的连边完全相同，那么把 $p$ 删去。（之所以要保留两个，是因为可以来回走，可能是优的。）

然后就通过了……\qiao。

可能是可以 hack 的，但是感觉 hack 也太累了吧。

代码实现上，感觉把这道题抬到了一个不属于它的高度。

代码

#include <bits/stdc++.h>
using namespace std;

const int MXN = 85;
const int LIM = 3;
const int CH = 37;
int N, K, val[MXN][MXN], ans(2e9);
bool disabled[MXN];
vector<pair<int, int>> choice1[MXN], choice2[MXN];
vector<pair<int, vector<int>>> mp1[MXN], mp2[MXN];

void dfs1(int p, vector<int>& path, int len) {
  if (path.size() == K / 2 - 1) {
    mp1[p].push_back(make_pair(len, path));
    if (mp1[p].size() > LIM) mp1[p].erase(max_element(mp1[p].begin(), mp1[p].end()));
    return;
  }
  for (int i(0); i != min(static_cast<int>(choice1[p].size()), CH); ++i) {
    int q(choice1[p][i].second);
    if (path.size() >= 3 && q == path[path.size() - 3]) continue;
    path.push_back(q);
    dfs1(q, path, len + val[p][q]);
    path.pop_back();
  }
}

void dfs2(int p, vector<int>& path, int len) {
  if (path.size() == K / 2 - 1) {
    mp2[p].push_back(make_pair(len, path));
    if (mp2[p].size() > LIM) mp2[p].erase(max_element(mp2[p].begin(), mp2[p].end()));
    return;
  }
  for (int i(0); i != min(static_cast<int>(choice2[p].size()), CH); ++i) {
    int q(choice2[p][i].second);
    if (path.size() >= 3 && q == path[path.size() - 3]) continue;
    path.push_back(q);
    dfs2(q, path, len + val[q][p]);
    path.pop_back();
  }
}

bool illegal(const vector<int>& path) {
  for (int i(1); i < path.size(); i += 2) {
    for (int j(0); j != path.size(); ++j) {
      if (path[(j + i) % path.size()] == path[j]) return true;
    }
  }
  return false;
}

int main() {
  cin >> N >> K;
  for (int i(0); i != N; ++i)
    for (int j(0); j != N; ++j) cin >> val[i][j];
  for (int i(1); i != N; ++i) {
    int cnt(0);
    for (int j(1); j != i; ++j) {
      if (disabled[j]) continue;
      bool same(true);
      for (int k(0); k != N; ++k)
        if (k != i && k != j && (val[k][i] != val[k][j] || val[i][k] != val[j][k]))
          same = false;
      cnt += same;
    }
    if (cnt >= 2) disabled[i] = true;
  }
  for (int i(0); i != N; ++i) {
    if (disabled[i]) continue;
    for (int j(0); j != N; ++j)
      if (j != i && !disabled[j])
        choice1[i].push_back(make_pair(val[i][j], j)),
        choice2[i].push_back(make_pair(val[j][i], j));
    sort(choice1[i].begin(), choice1[i].end());
    sort(choice2[i].begin(), choice2[i].end());
  }
  vector<int> tmp;
  dfs1(0, tmp, 0);
  dfs2(0, tmp, 0);
  for (int i(0); i != N; ++i) {
    for (int j(0); j != N; ++j) {
      for (int a(0); a != mp1[i].size(); ++a) {
        for (int b(0); b != mp2[j].size(); ++b) {
          for (int k(0); k != N; ++k) {
            vector<int> path(mp1[i][a].second);
            path.push_back(k);
            for (int d(K / 2 - 2); ~d; --d) path.push_back(mp2[j][b].second[d]);
            path.push_back(0);
            if (!illegal(path)) {
              ans = min(ans, mp1[i][a].first + val[i][k] + val[k][j] + mp2[j][b].first);
            }
          }
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}