数字校园建设专题网站,网页制作中的网站维护,制作人iu,微信小程序自助建站正题
题目链接:https://www.luogu.com.cn/problem/AT4437 题目大意
有nnn个点的一张有向完全图#xff0c;每个点有两个点权a,ba,ba,b。连接x,yx,yx,y两个点的边权为min{ax,by}min\{a_x,b_y\}min{ax,by}#xff0c;求一条权值和最小的哈密顿回路。 1≤n≤105,1≤a,b≤1…正题
题目链接:https://www.luogu.com.cn/problem/AT4437 题目大意
有nnn个点的一张有向完全图每个点有两个点权a,ba,ba,b。连接x,yx,yx,y两个点的边权为min{ax,by}min\{a_x,b_y\}min{ax,by}求一条权值和最小的哈密顿回路。
1≤n≤105,1≤a,b≤1091\leq n\leq 10^5,1\leq a,b\leq 10^91≤n≤105,1≤a,b≤109 解题思路
又是minminmin又是权值最小我们可以把问题转换为从xxx走到yyy的权值可以选择axa_xax或者byb_yby然后求最小的权值和。
一个暴力的想法是对于每个axa_xax对应一个byb_yby来匹配但是这样很显然容易导致选出的是若干个小环。
我们可以考虑具体一个点的贡献我们根据aaa和bbb是否产生了贡献记为一个二进制位那么每个点的贡献有00,01,10,1100,01,10,1100,01,10,11考虑什么时候一个方案合法。
把每个a/ba/ba/b视为一个二分图并且aia_iai向bib_ibi连边然后我们之后连的边中要求两个端点恰好有一个111确立如下图所示规则
110010/01/ring110010/01/ring110010/01/ring010101/ring010101/ring010101/ring同理有101010/ring101010/ring101010/ring0001/10000001/10000001/10001101/10111101/10111101/1011
不难发现一个合法的构造只有两种情况
全部都是010101或者101010000000和111111各有k(k≥1)k(k\geq 1)k(k≥1)个其余01/1001/1001/10任意
第一种情况直接计算
第二种情况我们对于每一个默认为01/1001/1001/10中权值最小的一个然后一个01/10→11(ansmax{ai,bi})01/10\rightarrow 11(ansmax\{a_i,b_i\})01/10→11(ansmax{ai,bi})一个01/10→00(ans−min{ai,bi})01/10\rightarrow 00(ans-min\{a_i,b_i\})01/10→00(ans−min{ai,bi})我们可以用两个堆分别维护max{ai,bi}max\{a_i,b_i\}max{ai,bi}和min{ai,bi}min\{a_i,b_i\}min{ai,bi}
需要注意的是由于第二种情况至少需要一个00/1100/1100/11所以就算第一次会让答案变大也得变而且有可能出现第一次选择的max{ai,bi}max\{a_i,b_i\}max{ai,bi}和min{ai,bi}min\{a_i,b_i\}min{ai,bi}是同一个iii需要特判。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define mp(x,y) make_pair(x,y)
#define ll long long
using namespace std;
const ll N1e510;
ll n,a[N],b[N],ans1,ans2,ans;
priority_queuepairll,ll q1,q2;
signed main()
{scanf(%lld,n);for(ll i1;in;i){scanf(%lld%lld,a[i],b[i]);ans1a[i];ans2b[i];q1.push(mp(min(a[i],b[i]),i));q2.push(mp(-max(a[i],b[i]),i));ansmin(a[i],b[i]);}pairll,ll xq1.top(),yq2.top();if(x.secondy.second){q1.pop();q2.pop();pairll,ll lq1.top(),rq2.top();ansmin(-r.first-x.first,-y.first-l.first);}else{q1.pop();q2.pop();ans-y.first-x.first;while(1){ll xq1.top().first,y-q2.top().first;q1.pop();q2.pop();if(xy)break;ansy-x;}}printf(%lld\n,min(ans,min(ans1,ans2)));return 0;
}
