[??记录]AT4437 [AGC028C] Min Cost Cycle

**题意** ：给出一张 $n$ 个点的有向图，其中 $u$ 点有点权 $A_u,B_u$ 。 对于 $u,v\ (u\neq v)$ ，边 $u\rightarrow v$ 的权值为 $\min(A_u,B_v)$。 求图的最短哈密顿环。 $n\leq 10^5$ ，时限$\texttt{2s}$。 ------------ 处理最优化问题的一类巧妙手段：将解集的约束简化（解集冗余化），利用最优化除去冗余的部分，做到将问题等价转化。 有时候只是灵机一动减少细节，有时则成为解题的关键。 如何简化约束？难点有两方面，一是“简化”不能导致不等价的转化；二是“简化”要足够强，足以使得我们能得到好做法。 一般来说，第一点比较直接，通过分析问题本身的性质就能处理；第二点则比较迂回，要通过题目中的碎片信息，以及经验，猜想出转化后的形式。 ------------ 本题题意较为简单，于是先从题目条件入手。 对于每个 $A_u,B_u$ ，只有“贡献”或“不贡献”两种可能。且最终一共有 $n$ 个数贡献了。 对于一个给定的有贡献的集合 $T$ ，考虑如何判定一个给定的哈密顿环是否合法。 一个显然的必要条件是 ： 对于每条边 $u\rightarrow v$ ，均满足 $A_u,B_v$ 恰有一个在 $T$ 中。 若只考虑这个条件，会产生冗余的解（即在某条边处选了较大值而非较小值），但不难证明这些解都是不优的。 接下来考虑如何判定一个给定的 $T$ 是否存在一种对应的哈密顿环。 将 $n$ 个点分为如下四类 ： - `00` ，$A_u,B_u\notin T$ 。 - `10` ，$A_u\in T,\ B_u\notin T$ 。 - `01` ，$A_u\notin T,\ B_u\in T$ 。 - `11` ，$A_u,B_u\in T$ 。 首先可以将所有的 `10` ， `01` 分别首尾相连，形成两条可以看做单个 `10` 或 `01` 的链。 若全为 `10` 或全为 `01` ，则可以直接形成一个大环。 若存在 `00` 与 `11` ，由 $|T|=n$ 不难证明两者个数相同。 若没有 `10` 和 `01` ，构造 `00` + `11` + `00` + `11` （交替）。 若有 `10` 和 `01` ，构造 `10` + `11` + `01` + `00` + `11` + `00` + `11`（交替）。 只剩下一种情况：不存在 `00` 和 `11` （每对 $A_u,B_u$ 恰被选中一个），且为 `10` 和 `01` 混杂。此时 `10` 和 `01` 之间无法连边，无解。 ------------ 得到了 $T$ 合法的充要条件，我们先来尝试考虑一些特殊方案（答案的下界）。 将 $A,B$ 混合排序（记结果为 $P_{1\sim 2n}$），取前 $n$ 小的作为 $T$ 。若合法，则显然是最优解。 若不合法，则将 $P_n$ 换成 $P_{n+1}$ ，若合法，则显然是最优解。 若仍然不合法，则说明 $P_n,P_{n+1}$ 分别为某点 $u$ 的 $A_u,B_u$ 。 此时考虑将 $P_{n+1}$ 换成 $P_{n+2}$ （导致 $A_u,B_u$ 同时不选），或者将 $P_{n-1}$ 换成 $P_n$ （导致 $A_u,B_u$ 同时选），不难发现这两个方案都必然合法，取最小值即可。 复杂度 $O(n\log n)$。 ------------ 总结：考察了最优化问题中“映射转化”、“冗余解集”两类经典技巧，且最终解法非常简洁，好题。 ```cpp #include<algorithm> #include<cstdio> #define MaxN 100500 #define ll long long using namespace std; struct Data{int x,p;}a[MaxN<<1]; bool cmp(const Data &A,const Data &B) {return A.x<B.x;} bool vis[MaxN<<1]; int n; bool chk() { int c10=0,c01=0; for (int i=1;i<=n+n;i+=2){ if (vis[i]&&!vis[i+1])c10++; if (!vis[i]&&vis[i+1])c01++; }return !(c10&&c01&&c10+c01==n); } int main() { scanf("%d",&n); for (int i=1;i<=n+n;i++){ scanf("%d",&a[i].x); a[i].p=i; }sort(a+1,a+n+n+1,cmp); long long ans=1ll<<60,sum=0; for (int i=1;i<=n;i++) {sum+=a[i].x;vis[a[i].p]=1;} if (chk())ans=min(ans,sum); vis[a[n].p]=0;vis[a[n+1].p]=1; sum+=a[n+1].x-a[n].x; if (chk())ans=min(ans,sum); vis[a[n+1].p]=0;vis[a[n+2].p]=1; sum+=a[n+2].x-a[n+1].x; if (chk())ans=min(ans,sum); vis[a[n+2].p]=vis[a[n-1].p]=0;vis[a[n+1].p]=vis[a[n].p]=1; sum+=a[n+1].x+a[n].x-a[n+2].x-a[n-1].x; if (chk())ans=min(ans,sum); printf("%lld",ans); return 0; } ```