(7/29) Basic board minimum spanning tree prim+kruskal

1.prim algorithm to find the minimum spanning tree

Given an undirected graph with nn points and mm edges, there may be multiple edges and self-loops in the graph, and the edge weights may be negative.

Find the sum of the tree edge weights of the minimum spanning tree. If the minimum spanning tree does not exist, output impossible.

Given an undirected graph G=(V,E)G=(V,E), where VV represents the set of points in the graph, EE represents the set of edges in the graph, n=|V|n=|V|, m=|E|m=|E|.

The undirected connected subgraph composed of all nn vertices in VV and n−1n−1 edges in EE is called a spanning tree of GG, and the spanning tree with the smallest sum of edge weights iscalled the minimum spanning tree of the undirected graph GG.

Input format

The first line contains two integers nn and mm.

The next mm lines, each line contains three integers u,v,wu,v,w, indicating that there is an edge with weight ww between point uu and point vv.

Output format

A total of one line, if there is a minimum spanning tree, output an integer, indicating the sum of the tree edge weights of the minimum spanning tree, if the minimum spanning tree does not exist, output impossible.

Data Range

1≤n≤5001≤n≤500,
1≤m≤1051≤m≤105,
The absolute value of the edge weights involved in the graph does not exceed 1000010000.

Sample input:

4 51 2 11 3 21 4 32 3 23 4 4

Sample output:

6

#include using namespace std;const int N=100010;int res=0;int mp[510][510];bool st[510];int dis[510];int n,m;const int inf=0x3f3f3f3f;int prim(){for(int i=0;imp[t][j])dis[j]=mp[t][j];}}return res;}int main(){int a,b,c;scanf("%d %d",&n,&m);memset(dis,inf,sizeof(dis));memset(mp,inf,sizeof(mp));while(m--){scanf("%d %d %d",&a,&b,&c);mp[a][b]=mp[b][a]=min(mp[a][b],c);}int t=prim();if(t==inf)printf("impossible\n");elseprintf("%d\n",t);return 0;}

2.kruskal algorithm

Given an undirected graph with nn points and mm edges, there may be multiple edges and self-loops in the graph, and the edge weights may be negative.

Find the sum of the tree edge weights of the minimum spanning tree. If the minimum spanning tree does not exist, output impossible.

Given an undirected graph G=(V,E)G=(V,E), where VV represents the set of points in the graph, EE represents the set of edges in the graph, n=|V|n=|V|, m=|E|m=|E|.

The undirected connected subgraph composed of all nn vertices in VV and n−1n−1 edges in EE is called a spanning tree of GG, and the spanning tree with the smallest sum of edge weights iscalled the minimum spanning tree of the undirected graph GG.

Input format

The first line contains two integers nn and mm.

The next mm lines, each line contains three integers u,v,wu,v,w, indicating that there is an edge with weight ww between point uu and point vv.

Output format

A total of one line, if there is a minimum spanning tree, output an integer, indicating the sum of the tree edge weights of the minimum spanning tree, if the minimum spanning tree does not exist, output impossible.

Data Range

1≤n≤1051≤n≤105,
1≤m≤2∗1051≤m≤2∗105,
The absolute value of the edge weights involved in the graph does not exceed 10001000.

Sample input:

4 51 2 11 3 21 4 32 3 23 4 4

Sample output:

6

Basic idea: first sort all edge weights according to their weights (stored in a structure), then enumerate each edge, use the union check set, if the two points are not in a connected block, thenAdd this edge to the set, and put the two points in the same connected block,

#include using namespace std;const int N=200010;int p[N];struct node{int st,ed,w;}a[N];int Find(int x){if(p[x]!=x)p[x]=Find(p[x]);return p[x];}bool cmp(struct node x,struct node y){return x.w