思路与算法

最大化每个武将的第二大关联边。超过这个阈值的边构成匹配，先选阈值见证的中心并利用电脑固定防守策略，随后阻断电脑的匹配边，可取到且保住严格胜利。

按上述模型建立状态或枚举对象，依代码中的顺序处理输入并输出完整答案。

正确性说明

令S为所有点的第二大关联边的最大值。若小涵先取得边权>S的一对，那么在取得第二端之前电脑已经根据第一端封锁唯一的>S邻居，故不可达。边权>S的边构成匹配。选择第二大边为S的中心u，电脑先拿它最大边的另一端v，小涵再取与u组成S的w。此后每当电脑拿到某条>S匹配边的一端，小涵优先拿另一端即可阻止电脑形成>S组合；v的唯一>S邻居已经是u，若没有待阻断者就任意取。所有边权互异，电脑也不能得到另一条等于S的边，所以小涵严格胜且最优值S。

复杂度

O(n²)时间、O(n)额外空间；逐边更新两端前两大值，不存矩阵。

易错点

矩阵仅给上三角，要同时更新两个端点的前两大值；边权全不同且n为至少4的偶数是证明前提。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<long long> a(n, -1), b(n, -1);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            long long w;
            cin >> w;
            for (int u : {i, j}) {
                if (w > a[u]) {
                    b[u] = a[u];
                    a[u] = w;
                } else if (w > b[u])
                    b[u] = w;
            }
        }
    cout << 1 << "\n" << *max_element(b.begin(), b.end()) << "\n";
}