AT4437[AGC028C]Min Cost Cycle【结论,堆】

正题

题目链接:https://www.luogu.com.cn/problem/AT4437

---

题目大意

有\(n\)个点的一张有向完全图，每个点有两个点权\(a,b\)。连接\(x,y\)两个点的边权为\(min\{a_x,b_y\}\)，求一条权值和最小的哈密顿回路。

\(1\leq n\leq 10^5,1\leq a,b\leq 10^9\)

---

解题思路

又是\(min\)又是权值最小，我们可以把问题转换为从\(x\)走到\(y\)的权值可以选择\(a_x\)或者\(b_y\)，然后求最小的权值和。

一个暴力的想法是对于每个\(a_x\)对应一个\(b_y\)来匹配，但是这样很显然容易导致选出的是若干个小环。

我们可以考虑具体一个点的贡献，我们根据\(a\)和\(b\)是否产生了贡献记为一个二进制位，那么每个点的贡献有\(00,01,10,11\)，考虑什么时候一个方案合法。

把每个\(a/b\)视为一个二分图，并且\(a_i\)向\(b_i\)连边，然后我们之后连的边中要求两个端点恰好有一个\(1\)，确立如下图所示规则：

1. \(11+00=10/01/ring\)
2. \(01+01=01/ring\)，同理有\(10+10=10/ring\)
3. \(00+01/10=00\)
4. \(11+01/10=11\)

不难发现一个合法的构造只有两种情况

1. 全部都是\(01\)或者\(10\)
2. \(00\)和\(11\)各有\(k(k\geq 1)\)个，其余\(01/10\)任意

第一种情况直接计算

第二种情况我们对于每一个默认为\(01/10\)中权值最小的一个，然后一个\(01/10\rightarrow 11(ans+max\{a_i,b_i\})\)，一个\(01/10\rightarrow 00(ans-min\{a_i,b_i\})\)，我们可以用两个堆分别维护\(max\{a_i,b_i\}\)和\(min\{a_i,b_i\}\)

需要注意的是由于第二种情况至少需要一个\(00/11\)所以就算第一次会让答案变大也得变，而且有可能出现第一次选择的\(max\{a_i,b_i\}\)和\(min\{a_i,b_i\}\)是同一个\(i\)，需要特判。

时间复杂度：\(O(n\log n)\)

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define mp(x,y) make_pair(x,y)
#define ll long long
using namespace std;
const ll N=1e5+10;
ll n,a[N],b[N],ans1,ans2,ans;
priority_queue<pair<ll,ll> > q1,q2;
signed main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++){
		scanf("%lld%lld",&a[i],&b[i]);
		ans1+=a[i];ans2+=b[i];
		q1.push(mp(min(a[i],b[i]),i));
		q2.push(mp(-max(a[i],b[i]),i));
		ans+=min(a[i],b[i]);
	}
	pair<ll,ll> x=q1.top(),y=q2.top();
	if(x.second==y.second){
		q1.pop();q2.pop();
		pair<ll,ll> l=q1.top(),r=q2.top();
		ans+=min(-r.first-x.first,-y.first-l.first);
	}
	else{
		q1.pop();q2.pop();
		ans+=-y.first-x.first;
		while(1){
			ll x=q1.top().first,y=-q2.top().first;
			q1.pop();q2.pop();
			if(x<=y)break;
			ans+=y-x;
		}
	}
	printf("%lld\n",min(ans,min(ans1,ans2)));
	return 0;
}