10.5最小生成树考试总结
题目总结
T1
正确思路：
一个很模版的模版题，只要算出两点之间的距离，然后跑最小生成树，注意边权小于c的边不可以通过。
AC Code
#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
#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
#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
#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;
}总结
这次有很多基础题都丢了分，还需巩固。