kuangbin专题六 最小生成树（2022.9.3）

4291. 丛林之路 - AcWing题库

题意

​ 丛林中有 $N$ 个村庄，每个村庄之间有若干双向通道，每个通道都有一定的权值，能在保持联通的情况下删除一些道路，求能删除道路权值的最大值。

题解

​ 最小生成树板题。

#include 
#include 
using namespace std;
const int N=26*75+10;
int n,m;
int p[N];
struct rec{
    int a,b,c;
}edges[N];
bool cmp(rec a,rec b){
    return a.c<b.c;
}
int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int kruskal(){
    sort(edges,edges+m,cmp);
    for(int i=0;i<n;i++)p[i]=i;
    int res=0,cnt=0;
    for(int i=0;i<m;i++){
        auto u=edges[i];
        int a=find(u.a),b=find(u.b);
        if(a!=b){
            p[a]=b;
            res+=u.c;
            cnt++;
        }
    }
    return res;
}

int main(){
    while(cin>>n,n){
        m=0;
        for(int i=0;i<n-1;i++){
            int x1;
            char c1;
            cin>>c1>>x1;
            while(x1--){
                int x2;
                char c2;
                cin>>c2>>x2;
                edges[m++]={(int)(c1-'A'),(int)(c2-'A'),x2};
            }
        }
        int ans=kruskal();
        cout<<ans<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

4292. 网络连接 - AcWing题库

题意

​ 给定一个 $n$ 个点和 $m$ 条边的连通图，求最小生成树。

题解

​ 最小生成树板题。

#include
using namespace std;
const int N=60,M=1510;
const int inf=0x3f3f3f3f;
/*-------------------------------------------------*/
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int prim(){
    memset(dist,0x3f,sizeof dist);

    int res=0;
    for (int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;

        if(i&&dist[t]==inf)return inf;
        if(i)res+=dist[t];
        st[t]=true;

        for(int j=1;j<=n;j++)
			dist[j]=min(dist[j],g[t][j]);
    }
    return res;
}
void solve(){
    while(cin>>n>>m,n){
        memset(g,0x3f,sizeof g);
        memset(st,false,sizeof st);
        while(m--){
            int a,b,c;
            cin>>a>>b>>c;
            g[a][b]=g[b][a]=min(g[a][b],c);
        }
    
        int ans=prim();
        if(ans==inf)puts("impossible");
        else cout<<ans<<endl;
    }
}
int main(){
    solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

4293. 建造空间站 - AcWing题库

题意

​ 在三位空间中有 $n$ 个球体，球体之间的连通有三种情况，①两球体相互接触或重叠，②两球体之间有通道，③两球体之间有间接通道。通道的长度是一个球的球面到另一个球的球面之间的最短距离。求要让所有球连通所需建造的通道最短距离是多少。

题解

​ 这一题没有直接给出边和权值，需要自行构造。同时在构造的时候还要判断题目中的条件，当两个球出现接触或重叠的情况时候就不需要再建立这条边了。

double dist(C a,C b){
    double dx=a.x-b.x,dy=a.y-b.y,dz=a.z-b.z;
    double dd=sqrt(dx*dx+dy*dy+dz*dz);
    if (dd-a.r-b.r<=0)return 0.0;
    else return dd-a.r-b.r;
}
1
2
3
4
5
6

​ 建立完所有边后就是最小生成树的板子了。

#include
#include
#include
#include
using namespace std;
const int N=110,M=20010;
int n,cnt,p[N];
struct Edge{
    int a,b;
    double w;
}e[M];
bool cmp(Edge a,Edge b){
	return a.w<b.w;
}
struct C{
    double x,y,z,r;
}c[N];
int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
double dist(C a,C b){
    double dx=a.x-b.x,dy=a.y-b.y,dz=a.z-b.z;
    double dd=sqrt(dx*dx+dy*dy+dz*dz);
    if (dd-a.r-b.r<=0)return 0.0;
    else return dd-a.r-b.r;
}
double kruskal(){
	sort(e,e+cnt,cmp);
	for(int i=0;i<N;i++)p[i]=i;
	double res=0;
    for (int i=0;i<cnt;i++){
    	auto t=e[i];
        int a=find(t.a),b=find(t.b);
        if (a!=b){
            p[a]=b;
            res+=t.w;
        }
    }
    return res;
}
void solve(){
	cnt=0;
	double x,y,z,r;
    for(int i=0;i<n;i++){
    	cin>>x>>y>>z>>r;
    	c[i]={x,y,z,r};
    }
    for(int i=0;i<n;i++){
    	for(int j=i+1;j<n;j++){
    		e[cnt++]={i,j,dist(c[i],c[j])};
    	}
    }
    double res=kruskal();
	printf("%.3lf\n",res);
}
int main(){
    while(cin>>n,n)solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

4294. 修建道路 - AcWing题库

题意

​ 有 $n$ 个村庄，给出 $n$ 个村庄直接的直线距离，有些村庄已经存在相连的道路，求要让所有村庄了连通所需的最短修路路径长度是多少。

题解

​ 本题主要处理已经有路径连接怎么处理，要是使用 $kruskal$ 算法，就在输入相连路径的时候同时在并查集上操作就行，使用 $prim$ 算法就将两村庄的路径变成 $0$。

#include 
#include
using namespace std;
const int N=110;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int prim(){
    memset(dist,0x3f,sizeof dist);
    int res=0;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;
        }
        if(i)res+=dist[t];
        st[t]=true;
        for(int j=1;j<=n;j++){
            dist[j]=min(dist[j],g[t][j]);
        }
    }
    return res;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>g[i][j];
        }
    }
    cin>>m;
    while(m--){
        int a,b;
        cin>>a>>b;
        g[a][b]=g[b][a]=0;
    }
    int res=prim();
    cout<<res<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

4295. QS网络 - AcWing题库

题意

​ 某星球上生活着 $n$ 只智慧生物，这些智慧生物想要相互之间直接或间接的实现网络通信。其中，每一条连接的两端需要使用网络适配器，且网络适配器不能重复使用，也就是说每一个链接都需要使用两个单独的网络适配器，每个智慧生物都有自己喜欢的网络适配器型号（只会使用喜欢的网络适配器），求之间相互连通的最小花费是多少。

题解

​ 这题读懂题意就很简单了，就在输入边的时候同时加上两端智慧生物喜欢的网络适配器需要的花费，然后就是板子了。

#include
#include
using namespace std;
const int N=500,M=N*N;
int _,n,m,a[N],g[N][N],dist[N];
bool st[N];
int prim(){
    memset(dist,0x3f,sizeof dist);
    memset(st,false,sizeof st);
    int res=0,cnt=0;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=0;j<n;j++){
            if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;
        }
        if(i)res+=dist[t];
        st[t]=true;
        for(int j=0;j<n;j++){
            dist[j]=min(dist[j],g[t][j]);
        }
    }
    return res;
}
void solve(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            cin>>g[i][j];
            g[i][j]+=a[i]+a[j];
        }
    int res=prim();
    cout<<res<<endl;
}
int main(){
    cin>>_;while(_--)
    solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

4332. 卡车历史 - AcWing题库

题意

​ 有 $N$ 个点，每个点使用一个长度为 $7$ 的由小写字母构成的字符串表示。每个点之间的距离是两个字符串对应位置上不同字母的个数。求最小生成树。

题解

​ 构造边，然后板子。注意多组输入。

#include
using namespace std;
const int N=2010,M=N*N;
int n,m;
string str[N];
struct Edge{
	int a,b,c;
}e[M];
bool cmp(Edge a,Edge b){
	return a.c<b.c;
}
int p[N];
int find(int x){
	if(p[x]!=x)p[x]=find(p[x]);
	return p[x];
}
int kruskal(){
	sort(e,e+m,cmp);
	for(int i=0;i<=n;i++)p[i]=i;
	int res=0;
	for(int i=0;i<m;i++){
		auto t=e[i];
		int a=find(t.a),b=find(t.b);
		if(a!=b){
			p[a]=b;
			res+=t.c;
		}
	}
	return res;
}
void solve(){
	while(cin>>n,n){
		m=0;
		for(int i=1;i<=n;i++){
	    	cin>>str[i];
	    }
	    for(int i=1;i<=n;i++){
	    	for(int j=i+1;j<=n;j++){
	    		int s=0;
	    		for(int k=0;k<7;k++){
	    			if(str[i][k]!=str[j][k])s++;
	    		}
	    		e[m++]={i,j,s};
	    	}
	    }
	    int res=kruskal();
		cout<<"The highest possible quality is 1/"<<res<<"."<<endl;
	}
}
int main(){
    solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

387. 北极网络 - AcWing题库

题意

​ 存在 $n$ 个哨站，在建立网络链接的时候有两种方式，①无线电收发器，②通信卫星。任意两个哨站之间无论距离都可以使用卫星进行通信，利用无线电则距离不能超过 $D$，卫星个数有限，无线电型号统一，求要让所有哨站直接或间接连通要的无线电收发距离 $D$ 的最小值是多少。

题解

​ 这题也需要自行构造边，然后再用板子，只要将和改成判断最大值就行。

#include
#include
#include
using namespace std;
typedef pair<double,double> pii;
#define x first
#define y second
const int N=2e5+10;
int _,n,m,p[N],cnt=0;
pii a[N];
struct Edge{
	int a,b;
	long double c;
}e[N];
bool cmp(Edge a,Edge b){
	return a.c<b.c;
}
int find(int x){
	if(p[x]!=x)p[x]=find(p[x]);
	return p[x];
}
long double kruskal(){
	sort(e,e+cnt,cmp);
	for(int i=0;i<=m;i++)p[i]=i;
	long double res=0;
	int s=0;
	for(int i=0;i<cnt;i++){
		if(s==m-n)break;
		auto t=e[i];
		int a=find(t.a),b=find(t.b);
		if(a!=b){
			p[a]=b;
			res=max(res,t.c);
			s++;
		}
	}
	return res;
}
long double dist(pii a,pii b){
	double dx=a.x-b.x;
	double dy=a.y-b.y;
	return sqrtl(dx*dx+dy*dy);
}
void solve(){
	cnt=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].x>>a[i].y;
	}
	for(int i=1;i<=m;i++){
		for(int j=i+1;j<=m;j++){
			e[cnt++]={i,j,dist(a[i],a[j])};
		}
	}
	long double res=kruskal();
	printf("%.2Lf\n",res);
}
int main(){
	cin>>_;while(_--)
	solve();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

4333. 高速公路 - AcWing题库

题意

​ 有 $N$ 个城市，其中有 $M$ 条已经存在的道路，要修建道路将所有城市连通，连通的

题解