題意

給定 \(n\)，對于每個 \(1\leq i,j\leq n\)，給出 \(d(i,j)\)。對于集合 \(S\)，定義 \(D(S)=\max\limits_{i,j\in S}d(i,j)\)。將 \(\{1,2,\cdots,n\}\) 劃分為兩個集合 \(A,B\)，最小化 \(D(A)+D(B)\)。\(1\leq n\leq 200\)。

題解

不妨欽定 \(D(A)\geq D(B)\)，考慮枚舉 \(A,B\) 中邊權最大的邊 \((a,b),(c,d)\)，那么對于每條不為 \((a,b),(c,d)\) 的邊 \((i,j)\)：

• 若 \(d(i,j)>d(a,b)\)，則 \(i,j\) 不能同時在 \(A\) 中。
• 若 \(d(i,j)>d(c,d)\)，則 \(i,j\) 不能同時在 \(B\) 中。

顯然是 2-SAT 的形式，直接做 Tarjan 判定是否有解就可以得到 \(\mathcal{O}(n^6)\) 的做法。

進一步優化，固定 \(A\) 中邊權最大的邊后，使用二分，check \(B\) 中的最大邊權能不能 \(\leq x\)。時間復雜度降到 \(\mathcal{O}(n^4\log{n})\)。

接下來是非常神仙的一步優化。我們從大到小枚舉 \(A\) 中邊權最大的邊，建一個新圖 \(G\)，每枚舉一條新邊，就把這條邊加入 \(G\) 中?？疾烊艏尤氘斍斑?\((i,j)\) 后，\(G\) 中形成一個環說明什么：

• 若該環為奇環，考察接下來某條將要枚舉的邊 \((i',j')\) 滿足 \(d(i',j')<d(i,j)\)，這時我們會要求前面的邊不能同時出現在 \(A\) 中，也不能同時出現在 \(B\) 中，相當于做二分圖染色，但是由于出現了奇環，必定無解。因此這種情況下，我們處理完當前邊后就不必繼續往后枚舉了。
• 若該環為偶環，則當前邊必定不能作為 \(A\) 中的最大邊。因為此時必然要求這條邊連接的兩個點同色，但是由于這兩個點之間間隔了奇數個點，顯然這是不可能的。因此這種情況下，我們直接跳過當前邊。

于是 \(G\) 中至多有 \(n\) 條邊，時間復雜度降為 \(\mathcal{O}(n^3\log{n})\)，可以通過。

實現時可以使用帶權并查集維護是否成環，以及連成了奇環還是偶環。

代碼

放一下主要部分。

struct DSU {
	int fa[N], c[N];
	inline void init() { for (int i = 1; i <= n; ++i) fa[i] = i, c[i] = 0; }
	inline int find(int x) {
		if (x == fa[x]) return x;
		int fx = fa[x];
		return fa[x] = find(fa[x]), c[x] ^= c[fx], fa[x];
	}
	inline void unite(int x, int y) {
		int fx = find(x), fy = find(y);
		if (fx == fy) return;
		fa[fx] = fy, c[fx] ^= c[x] ^ c[y] ^ 1;
	}
} d;

inline void tarjan(int x) {
	low[x] = dfn[x] = ++stmp, in_stk[stk[++top] = x] = 1;
	for (int y : G[x]) {
		if (!dfn[y]) tarjan(y), chk_min(low[x], low[y]);
		else if (in_stk[y]) chk_min(low[x], dfn[y]);
	}
	if (low[x] == dfn[x]) {
		++tot; int p;
		do p = stk[top--], in_stk[p] = 0, id[p] = tot; while (p != x);
	}
}
inline bool sat(int w1, int w2) {
	for (int i = 1; i <= n << 1; ++i) G[i].clear();
	for (int i = 1; i <= sze; ++i) {
		int x = e[i].x, y = e[i].y, z = e[i].z;
		if (z > w1) G[x].push_back(y + n), G[y].push_back(x + n);
		if (z > w2) G[x + n].push_back(y), G[y + n].push_back(x);
	}
	fill(dfn + 1, dfn + (n << 1) + 1, 0), stmp = tot = 0;
	for (int i = 1; i <= n << 1; ++i) if (!dfn[i]) tarjan(i);
	for (int i = 1; i <= n; ++i) if (id[i] == id[i + n]) return 0;
	return 1;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) for (int j = i + 1, w; j <= n; ++j) cin >> w, e[++sze] = {i, j, w};
	if (n <= 2) return cout << "0", 0;
	sort(e + 1, e + sze + 1), d.init();
	for (int i = sze; i; --i) {
		int x = e[i].x, y = e[i].y, fx = d.find(x), fy = d.find(y);
		if (fx != fy) d.unite(x, y);
		else if (d.c[x] != d.c[y]) continue;
		int l = 0, r = i - 1, mn = INF;
		while (l <= r) {
			int mid = l + r >> 1;
			if (sat(e[i].z, e[mid].z)) mn = e[mid].z, r = mid - 1;
			else l = mid + 1;
		}
		chk_min(ans, e[i].z + mn);
		d.find(x), d.find(y);
		if (d.c[x] == d.c[y]) break;
	}
	cout << ans;
	return 0;
}