[AGC028C] Min Cost Cycle

Description

  给定一个 \(n\) 条边的有向完全图，每个点有两个点权 \(a,b\) 一条边 \((u,v)\) 的权值为 \(\min(a_u,b_v)\) 。
  求边权和最小的哈密顿回路的边权和。
   \(2\leq n\leq 10^5, 1\leq a,b\leq 10^9\) 。

Solution

Phase 1

  首先既然是哈密顿路，那么一定会经过所有的 \(a_i, b_i\) 各一次。那么通过这一点，我们可以把题目的重心从图的结构中移开，去更多地关注点的性质。先不考虑合法性，令对最终答案有贡献的数的集合为 \(T\) ，那么点的结构无非 \(4\) 种：

• ① \(a_i\in T 且 b_i\in T\)

• ② \(a_i\not\in T 且 b_i\in T\)

• ③ \(a_i\in T 且 b_i\not\in T\)

• ④ \(a_i\not\in T 且 b_i\not\in T\)

（图中的箭头表示有向边，而包含有向边的点表明该有向边的 \(\min(a,b)\) 在该点上）

  接下来就是考虑如何把所有点拼成一个环。
  首先发现②可以全部首尾相接等价地缩成一个②，③也同理。一个很显然的拼法是在全部点都是②或③的情况下，首尾相接拼成一个环，如果既有②也有③且无①、④，那么是无法拼成一个点的。考虑有①、④的情况，由于 \(|T| = n\) ，所以①④的数量一定是相等的那么可以通过在一个④左边拼上③（如果有③的话），右边拼上②（如果有②的话），然后在③②间交替插入①④，像这样：

即是一种拼法。

Phase 2

  我们考虑一个贪心的构造，钦定将 \(a,b\) 放在一起排序完后最小的 \(n\) 个值为答案，并检测其正确性。
  稍微总结一下 Phase 1 便不难得到，有且仅有一种情况是无法拼成环的，那就是每个点有各有一个 \(a/b\) 且不全为 \(a\) 或 \(b\) 。
  在这之后我们继续贪心地考虑，即在答案中删掉第 \(n\) 小的值然后加上第 \(n+1\) 小的值。这次仅有一种极端的情况不合法，即第 \(n,n+1\) 为同一个点的 \(a,b\) 且仍没有形成全为 \(a\) 或 \(b\) 的情形，并没有改变前一种情形我们所提到的不合法性质。剩下的两种贪心变换方式一定是合法的，取答案取最小即可。

Code

int tax[N], typ[2];
struct BLCK{LL val, id, c;}a[N];

int main() {
	int n = read(), cntn = 0, flag = 0;
	LL ans = 0;
	rep (i, 1, n)	a[++cntn] = (BLCK){read(), i, 0}, a[++cntn] = (BLCK){read(), i, 1};
	sort(a+1, a+1+cntn, [&](BLCK x, BLCK y){return x.val < y.val;});
	rep (i, 1, n) flag |= (++tax[a[i].id] > 1), ans += a[i].val, ++typ[a[i].c];
	if (flag || max(typ[0], typ[1]) == n) return printf("%lld\n", ans), 0;
	ans += a[n+1].val-a[n].val, --typ[a[n].c], ++typ[a[n+1].c];
	if (a[n].id != a[n+1].id || max(typ[0], typ[1]) == n) return printf("%lld\n", ans), 0;
	printf("%lld\n", min(ans-a[n+1].val+a[n+2].val, ans-a[n-1].val+a[n].val));
	return 0;
}

Summary

  分析问题时，可以考虑从图的性质入手，将问题的本质提炼出来，转化问题为更易求解的形式。