AT_arc212_a [ARC212A] Four TSP Solution(附带启发式)

· · 算法·理论

启发式版本

依旧 ARC T1 放水。

明显可以走“先暴力，然后优化”的路线。

注意到顶点数为 4 这个性质，尝试推理所有的哈密尔顿回路的可能经过边情况。

设图上四个点从左上开始依次为 A,B,C,D。

则很明显，只有 3 种从 A 出发的不同哈密尔顿回路：

  1. A \to B \to D \to C \to A
  2. A \to B \to C \to D \to A
  3. A \to C \to B \to D \to A

注意到可以合并对边 AB,CD 的枚举，对边 AC,BD 的枚举，对边 AD,BC 的枚举，将它们合并为 3 组（因为同一组中的两条边在任意哈密尔顿回路中一定要么都经过要么都不经过）。

因此，其实只需要枚举前 2 组边权值和 v_1、v_2，第 3 组边权值和 v_3 即可确定。计算答案时要乘上 (v_1-1)(v_2-1)(v_3-1)（这相当于拆这些组为两条单边）。

注意取 \max，以及判重。

时间复杂度 \Theta(n^2)。

:::info[参考代码]

#include<bits/stdc++.h>
using namespace std;
typedef long long li;
const int moi=998244353;
int h(int x, int y) {
    return (x%moi+y%moi)%moi;
}
int g(int x, int y) {
    return ((x%moi-y%moi)%moi+moi)%moi;
}
int f(int x, int y) {
    return (((1ll*x)%moi)*(y%moi))%moi;
}
int ans;
int main() {
    int n;
    cin >> n;
    int lm=n/3;
    for(int k1=2; k1<=lm; k1++) {
        int ly=((n-k1)>>1);
        for(int k2=k1; k2<=ly; k2++) {
            int ci=1;
            int cnt=0;
            if(k1^k2) cnt++;
            if(k1^(n-k1-k2)) cnt++;
            if((n-k1-k2)^k2) cnt++;
            if(cnt>2) ci=6;
            else if(cnt) ci=3;
            ans=h(ans, f(f(f(k1-1, k2-1), f(n-k1-k2-1, ci)), k1+k2));
        }
    }
    cout << ans;
    return 0;
}
//咕咕咕！

:::

:::info[以此祭我的这篇题解]

专栏文章审核结果 2026-04-28 07:00 很遗憾，您的《题解：AT_arc212_a [ARC212A] Four TSP》不符合推荐标准。原因是：同一个数学公式应写在一个 LaTeX 环境内，不应分开写，例如 a + b = c 不应写为 a + b = c 或 a + b = c。。

专栏文章审核结果 2026-04-25 10:20 很遗憾，您的《题解：AT_arc212_a [ARC212A] Four TSP》不符合推荐标准。原因是：滥用折叠框。

专栏文章审核结果 2026-04-24 20:25 很遗憾，您的《题解：AT_arc212_a [ARC212A] Four TSP》不符合推荐标准。原因是：则上请不要在数学公式中加中文，变量条件请定义英文变量、逻辑条件请使用集合符号。。｜审核管理员：happy_zero，对审核结果有疑问请私信交流。

:::