题解：P10768 「CROI · R2」落月摇情

昨夜闲潭梦落花，可怜春半不还家。

江水流春去欲尽，江潭落月复西斜。

Solution P10768

Problem 1

这

m

条边的构成是什么？

Solution to Problem 1

首先，

m

条边一定是：原图的 MST 与剩下的边里面选

m-(n-1)

条。

证明是显然的：你要保证所有点都联通，所以你选择一个 MST。现在联通了，那你贪心的选择最小的加进去就行。

Problem 2

如何求 MST？

Solution to Problem 2

不难发现：

如果 $a_i<0$ ，则你给他连上 $a_i$ 的最大值位置最佳；
如果 $a_i>0$ ，则你给他连上 $a_i$ 的最小值最佳；
如果 $a_i=0$ ，你随便连，归到上面一类解决。

解决了 MST 问题。

Problem 3

如何往上面加非 MST 边？

Solution to Problem 3

很显然可以把所有边都算一遍排个序，但是复杂度

\operatorname{O}(n^2)

，会爆炸。

你可以先对

a

排序，然后维护一个堆。

设

p_i

为排序之后对应位置为

i

的点。

那么你会发现：如果某个点

k

权值

>0

，则如果

(p_1,k)

还没有被计算，

(p_2,k)

进入这个堆是无意义的，因为

w_{(p_2,k)}>w_{(p_1,k)}

，我们在算到

(p_1,k)

的时候再把

(p_2,k)

塞进去就行了。

同理，小于

0

的时候，就是从

(p_n,k)

开始处理，如果处理到了就把

(p_{n-1},k)

塞进去。

这样你只会处理

m

次加边操作，复杂度

\operatorname{O}(m\log n)

。

小问题

两步中，MST 中的边可能会被第二步也处理到。加上 MST 中的边也可能发生重复（例如

a=\{-1,1\}

，那么处理

1

时会处理

(1,2)

，处理

2

时处理的还是

(1,2)

，所以如何判重边？

Solution

最简单的想法是拿一个 map 存一下这条边是不是被加了，但是常数太大加之带

\log

T 飞了。

于是改用 gp_hash_table，这是一个 pb_ds 库里的东西，在 CCF 系列竞赛中可以使用。在日常调试中，需要：

CPP

#include<bits/extc++.h>
using namespace __gnu_pbds;

AC Code

CPP

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ls (now<<1)
#define rs ((now<<1)|1)
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
const int N=1000005;
const int mod=1;
const int intinf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
struct node{
	ll w;
	int u,v;
	friend bool operator <(node _,node __){
		return _.w>__.w;
	}
};
node make_node(int u,int v,ll w){
	node rrat;
	rrat.u=u;
	rrat.v=v;
	rrat.w=w;
	return rrat;
}
gp_hash_table<int,int>mp[N];
std::priority_queue<node>q;
struct Node{
	int a,id;
	friend bool operator <(Node _,Node __){
		return _.a<__.a;
	}
}A[N];
ll a[N];int id[N];
int n,m;
ll sum=0;
vector<pair<int,int> >ans;
void add(int u,int v){
	if(mp[u][v]||u==v)return;
	ans.push_back(make_pair(u,v));
	mp[u][v]=1;mp[v][u]=1;
	sum+=a[u]*a[v];
} 
signed main(){
	fastio;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>A[i].a;A[i].id=i;
	}
	sort(A+1,A+n+1);
	for(int i=1;i<=n;i++){
		a[i]=A[i].a;
		id[i]=A[i].id;
	} 
	for(int i=1;i<=n;i++){
		if(a[i]<0){
			add(i,n);
			q.push(make_node(i,n,a[i]*a[n]));
		}
		else {
			add(i,1);
			q.push(make_node(i,1,a[i]*a[1]));
		}
	}
	int cnt=n-1;
	while(!q.empty()&&cnt<m){
		node tmp=q.top();q.pop();
		int u=tmp.u,v=tmp.v;
		if(a[u]>=0){
			if(v!=n)q.push(make_node(u,v+1,a[u]*a[v+1]));
		}
		else{
			if(v!=1){
				q.push(make_node(u,v-1,a[u]*a[v-1]));
			}
		}
		if(mp[u][v])continue;
		if(u==v)continue;
		cnt++;
		add(u,v);
	}
	cout<<sum<<'\n';
	for(auto p:ans){
		cout<<id[p.fi]<<' '<<id[p.se]<<'\n';
	} 
	return 0;
}

题解：P10768 「CROI · R2」落月摇情

文章操作

Solution P10768

相关推荐

评论

题解：P10768 「CROI · R2」落月摇情