NOIP三国游戏：图论与博弈论的完美结合

发布时间：2026/11/4 3:13:19

1. 三国游戏题目解析与解题思路

作为一名参加过多次信息学竞赛的老选手，第一次看到这道题时就被它巧妙的博弈设计吸引了。这道来自NOIP2010普及组的题目看似简单，却融合了图论、贪心和博弈论的思想，非常考验选手的综合分析能力。

1.1 题目模型构建

题目描述的是三国时期武将之间的默契值，我们可以将其抽象为一个图论模型：

每个武将对应图中的一个顶点
任意两个武将之间的默契值就是连接这两个顶点的边的权值
由于每两个武将之间都有默契值，因此这是一个完全图（任何两个顶点之间都有边相连）

这个邻接矩阵的特点是：

对角线上的值无意义（自己与自己的默契值）
矩阵是对称的（g[i][j] = g[j][i]）

1.2 游戏规则分析

游戏规则可以这样理解：

玩家和电脑轮流选择武将（顶点）
选择结束后，计算玩家所选武将之间的最大默契值（边权），以及电脑所选武将之间的最大默契值
比较这两个值，较大的一方获胜

关键在于电脑的选择策略：当玩家选择一个武将后，电脑一定会选择与该武将默契值最高的那个武将。这实际上剥夺了玩家获取最大默契值的机会，但同时也给了玩家一个突破口。

2. 必胜策略的发现与证明

2.1 玩家必胜的直觉理解

经过多次模拟后，我发现玩家总是有必胜策略。这是因为：

玩家先手选择任意一个武将A
电脑被迫选择与A默契值最高的武将B（根据游戏规则）
这样玩家和电脑都无法获得AB这条边（最大默契值）
但玩家可以在下一步选择与A默契值次高的武将C，获得AC这条边

由于玩家是先手，可以主动选择让次大值最大的那个武将组合，从而确保自己获得的默契值总是所有可能的次大值中最大的。

2.2 严格的数学证明

为了更严谨地证明这个结论，我们可以这样思考：

对于图中的每个顶点v，设：

max1(v) 表示与v相连的最大边权
max2(v) 表示与v相连的次大边权

玩家策略：

选择一个顶点v，使得max2(v)是所有顶点中最大的
电脑会选择与v相连的max1(v)对应的顶点u
玩家再选择与v相连的max2(v)对应的顶点w

这样玩家获得的边vw的权值就是max2(v)，而电脑获得的边vu的权值是max1(v)。但由于游戏规则规定比较的是各自阵营内部的最大值，而玩家只有w一个武将（暂时），电脑有u一个武将，此时双方都只有一个武将，没有内部边。

随着游戏进行，玩家总能确保自己获得的边权是所有可能次大值中最大的，因此最终玩家阵营内部的最大边权一定不小于电脑阵营的。

3. 算法实现与优化

3.1 基础解法思路

根据上述分析，解题步骤可以分解为：

构建完整的邻接矩阵
对每个顶点（矩阵的每一行），找出次大值
所有次大值中的最大值就是答案

3.2 两种高效实现方法

3.2.1 维护最大值和次大值变量

这是最直观的方法，时间复杂度O(n^2)：

int ans = 0; for(int i = 1; i <= n; ++i) { int max1 = 0, max2 = 0; for(int j = 1; j <= n; ++j) { if(g[i][j] >= max1) { max2 = max1; max1 = g[i][j]; } else if(g[i][j] > max2) { max2 = g[i][j]; } } ans = max(ans, max2); }

注意：这里需要跳过i==j的情况，因为自己与自己的默契值无意义。

3.2.2 使用双元素链表

这是一种更巧妙的实现，虽然实际性能可能不如第一种，但展示了不同的思路：

list<int> lis{0,0}; // front: max1, back: max2 for(int j = 1; j <= n; ++j) { if(g[i][j] >= lis.front()) { lis.push_front(g[i][j]); lis.pop_back(); } else if(g[i][j] > lis.back()) { lis.pop_back(); lis.push_back(g[i][j]); } } ans = max(ans, lis.back());

3.3 输入处理的注意事项

在实际编码中，输入处理有几个关键点：

题目给出的默契值只包含上三角部分（i < j），需要手动填充下三角部分
矩阵对角线不需要处理
默契值都是正整数，可以安全地用0初始化

for(int i = 1; i <= n; ++i) for(int j = i+1; j <= n; ++j) { cin >> g[i][j]; g[j][i] = g[i][j]; // 对称填充 }

4. 复杂度分析与优化思考

4.1 时间复杂度分析

两种方法的时间复杂度都是O(n^2)，因为：

需要遍历所有n个顶点
对于每个顶点，需要遍历其n-1个邻居
每次更新最大值和次大值是O(1)操作

4.2 可能的优化方向

虽然O(n^2)已经是最优复杂度（因为必须读取所有n(n-1)/2个输入数据），但还可以考虑：

并行计算：每行的处理是独立的，可以并行处理
内存访问优化：按行存储比按列存储访问效率更高
输入优化：使用快速输入方法处理大规模数据

4.3 实际比赛中的选择

在竞赛中，我推荐使用第一种方法（维护两个变量），因为：

实现简单，不易出错
常数因子小，实际运行速度快
代码可读性好，便于调试

第二种方法虽然巧妙，但使用链表会带来额外的开销，而且对于这个问题并没有明显的优势。

5. 常见错误与调试技巧

5.1 新手常见错误

忘记填充对称矩阵：
- 只读取了上三角部分，没有设置g[j][i] = g[i][j]
- 导致某些边的权值为0或未定义
错误处理对角线元素：
- 错误地将g[i][i]纳入最大值比较
- 实际上对角线元素应该被忽略
次大值更新逻辑错误：
- 没有正确处理等于当前最大值的情况
- 次大值应该总是小于等于最大值

5.2 调试技巧

小规模测试：
- 先用n=3的小例子手动计算验证
- 确保基本逻辑正确
打印中间结果：
- 输出邻接矩阵检查对称性
- 打印每行的最大值和次大值
边界测试：
- 测试n=1的特殊情况
- 测试所有默契值相同的情况

5.3 我的踩坑经历

在实际解题过程中，我最初犯了一个错误：认为玩家需要选择特定的顶点才能获胜。后来通过画图分析才发现，无论玩家先选哪个顶点，只要按照策略选择次大值，就一定能获胜。这个认识上的突破让我明白了博弈类题目往往有全局的最优策略，而不是依赖于特定的初始选择。

6. 代码实现细节解析

6.1 完整代码实现

#include<bits/stdc++.h> using namespace std; const int N = 505; int n, g[N][N], ans; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for(int i = 1; i < n; ++i) for(int j = i+1; j <= n; ++j) { cin >> g[i][j]; g[j][i] = g[i][j]; } for(int i = 1; i <= n; ++i) { int max1 = 0, max2 = 0; for(int j = 1; j <= n; ++j) { if(i == j) continue; if(g[i][j] >= max1) { max2 = max1; max1 = g[i][j]; } else if(g[i][j] > max2) { max2 = g[i][j]; } } ans = max(ans, max2); } cout << "1\n" << ans; return 0; }