专栏文章

10.5最小生成树考试总结

ccaizimo
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minougxj
此快照首次捕获于
2025/12/02 05:55
3 个月前
此快照最后确认于
2025/12/02 05:55
3 个月前
查看原文

题目总结

T1

正确思路：

一个很模版的模版题，只要算出两点之间的距离，然后跑最小生成树，注意边权小于c的边不可以通过。

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=5e6+10;
struct node{
	int x,y,w;
}e[N];
bool cmp(node x,node y){
	return x.w<y.w;
}
int n,c,x[N],y[N],tot,fa[N],cnt,ans;
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void unionn(int x,int y){
	x=find(x); y=find(y);
	if(x!=y){
		fa[x]=y;
	}
	return ;
}
int dist(int i,int j){
	int a=(x[i]-x[j])*(x[i]-x[j]);
	int b=(y[i]-y[j])*(y[i]-y[j]);
	int q=a+b;
	return q;
}
void kruskal(){
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=tot;i++){
		if(find(e[i].x)==find(e[i].y)) continue;
		if(e[i].w<c) continue;//边权小于c不能走
		ans+=e[i].w;
		unionn(e[i].x,e[i].y);
		cnt++;
		if(cnt==n-1) return ; 
	}
	return ;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>c;
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
	tot=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			e[++tot].x=i;
			e[tot].y=j;
			e[tot].w=dist(i,j);//算出任意两点距离
		}
	}
	sort(e+1,e+1+tot,cmp);
	kruskal();//跑kruskal算法，prim更好但我没学
	if(cnt<n-1) cout<<-1;
	else cout<<ans;
	return 0;
}

T2

错误原因

开了double,原题的距离不需要开根号，所以不用也不能开double。

正确思路

一道更模版的板子题，只需要求两点距离，然后跑最小生成树，并记录最后连接的边权，因为排了序，所以最后的就是最大的边。

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
struct node{
	int x,y,w;
}e[N];
bool cmp(node x,node y){
	return x.w<y.w;
}
int n,tot,fa[N],cnt,ans,x[N],y[N];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void unionn(int x,int y){
	x=find(x); y=find(y);
	if(x!=y){
		fa[x]=y;
	}
	return ;
}
double dist(int i,int j){
	double a=(x[i]-x[j])*(x[i]-x[j]);
	double b=(y[i]-y[j])*(y[i]-y[j]);
	double q=a+b;
	return q;
}
void kruskal(){
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=tot;i++){
		if(find(e[i].x)==find(e[i].y)) continue;
		ans=max(ans,e[i].w);
		unionn(e[i].x,e[i].y);
		cnt++;
		if(cnt==n-1) return ; 
	}
	return ;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
	tot=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			e[++tot].x=i;
			e[tot].y=j;
			e[tot].w=dist(i,j);
//			cout<<e[tot].w<<endl;
		}
	}
	sort(e+1,e+1+tot,cmp);
	kruskal();
	cout<<ans;
	return 0;
}

T3

错误原因

没开longlong

正确思路

还是比较模版，跟上一题一样，只要多记录几个值：用的是点权还是边权，并输出，题目有点长，但是还算简单\

一定要开longlong!!别问我咋知道的

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long 
typedef long long ll;
const int N=4e6+10;
struct node{
	int x,y,w;
}e[N];
bool cmp(node x,node y){
	return x.w<y.w;
}
int n,tot,fa[N],ans,sum1,sum2,x[N],y[N],c[N],k[N];
vector<int> res1;
vector<node> res2;
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void unionn(int x,int y){
	x=find(x); y=find(y);
	if(x!=y){
		fa[x]=y;
	}
	return ;
}
int dist(int i,int j){
	int a=abs(x[i]-x[j]);
	int b=abs(y[i]-y[j]);
	return a+b;
}
int kruskal(){
	for(int i=1;i<=n+1;i++) fa[i]=i;
	for(int i=1;i<=tot;i++){
		if(find(e[i].x)==find(e[i].y)) continue;
		ans+=e[i].w;
		if(e[i].x==n+1) res1.push_back(e[i].y);
		else res2.push_back({e[i].x,e[i].y});
		unionn(e[i].x,e[i].y);
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
	for(int i=1;i<=n;i++) cin>>c[i];
	for(int i=1;i<=n;i++) cin>>k[i];
	tot=0;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			e[++tot].x=i;
			e[tot].y=j;
			e[tot].w=dist(i,j)*(k[i]+k[j]);
		}
	}
	for(int i=1;i<=n;i++){
		e[++tot].x=n+1;
		e[tot].y=i;
		e[tot].w=c[i];
	}
	sort(e+1,e+1+tot,cmp);
	cout<<kruskal()<<endl;
	cout<<res1.size()<<endl;
	for(auto x : res1) cout<<x<<' ';
	cout<<endl;
	cout<<res2.size()<<endl;
	for(auto x : res2) cout<<x.x<<' '<<x.y<<endl;
	return 0;
}

T4

正确思路

这题不能暴力，时间空间都炸了，所以我们以区间为单位处理，我们发现每次加边都是一个连通块，而连通块必然是一片连续的区间，假设我们在维护并查集的时候，尽量往右边合并，那么在数区间时，可以直接跳到这个连通块的右端点，跳过了中间很多循环遍历的过程，一直到这个点该联的区间即可。

AC Code

CPP
#include<bits/stdc++.h>
#define int long long
#define qwq i
using namespace std;
const int N = 2e5+5;
struct node{
	int l,r,c;
	bool operator < (const node & tmp) const {
		return c < tmp.c;
	}
}a[N];
int n,q,fa[N];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
int kruskal() {
	for (int i=1; i<=n; i++) fa[i] = i;
	int sum=0;
	for (int i=1;i<=q;i++) {
		int l=a[i].l,r=a[i].r,c=a[i].c;
		sum+=c;  
		l=find(l),r=find(r);
		while(l!=r){
			sum+=c;
			fa[l]=l+1;
			l=find(l);
		}
	}
	if(find(1)==find(n)) return sum;
	return -1;
}
signed main() {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=q;i++) cin>>a[i].l>>a[i].r>>a[i].c;
	sort(a+1,a+1+q);
	cout<<kruskal();
	return 0;
}

总结

这次有很多基础题都丢了分，还需巩固。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...