题解：Luogu P6898 [ICPC 2014 WF] Metal Processing Plant

题意

给定 \(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;
}