2022.2.15

Minimum spanning tree （kruskal Algorithm ）

All the questions today , I use it all. kruskal Algorithm to do .

Tomorrow with prim Algorithm to solve individual problems , Personally feel prim Algorithm and dijkstra The algorithm is a little similar , So learn first kruskal Algorithm .

kruskal The algorithm uses a union search set and an array of edge sets .

1. The function of union search set is to judge whether a ring is formed . It is necessary to initialize when using the parallel search set .

2. The edge set array is sorted by the weight .

struct node{
	int begin;// starting point 
    int end;// The end point 
    int v;// The weight 
}lu[max];
bool com(node a,node b)
{
	return a.v<b.v;// hold lu[] Sort by weight from small to large  
}
sort(lu+1,lu+m+1,com);// to lu The array is sorted by weight  

【 Templates 】 Minimum spanning tree

subject P3366 【 Templates 】 Minimum spanning tree - Luogu | New ecology of computer science education (luogu.com.cn)

Answer key ： This topic is simple kruskal Algorithm template problem , There is nothing to explain .

        1. Two arrays ： An edge set array and a union search set array .

        2. Note that whether the figure below is connected is to judge whether a tree has been formed , That is, the number of connected edges is the total number of vertices n-1.

The code is as follows ：

#include<bits/stdc++.h>
#define max 1e4+10 
int f[5009],n,m,ans,a;
using namespace std;
struct node{
	int be,end,v;
}lu[200009];
bool com(node a,node b)
{
	return a.v<b.v;// Sort from small to large  
}
int find(int x)// Union checking set  
{
	if(x==f[x])
	return x;
	else
	f[x]=find(f[x]);
	return f[x];
}
void kru()
{
	int i,x,y;
	sort(lu+1,lu+m+1,com);// to lu The array is sorted by weight  
	for(i=1;i<=n;i++)
	f[i]=i;// And search set initialization  
	for(i=1;i<=m;i++)
	{
		x=find(lu[i].be);
		y=find(lu[i].end);
		if(x!=y)// No loop formed  
		{
			f[x]=y;
			ans+=lu[i].v;
			a++;
			if(a==n-1)// The condition of forming a tree is to have the total number of vertices n-1 edge 
			break;
		}
	}
}
int main()
{
	int i;
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		cin>>lu[i].be>>lu[i].end>>lu[i].v;
	}
	kru();
	if(a==n-1)
	cout<<ans;
	else if(a!=n-1)
	printf("orz");
	return 0;
}

Take down the carpet

subject P2121 Take down the carpet - Luogu | New ecology of computer science education (luogu.com.cn)

Answer key ： This topic is similar to the last one , The difference is that the sorting is based on the weight from large to small . The final judgment is whether the number of connecting edges is equal to K, If yes, call up . Output the beauty value added at this time .

The code is as follows ：

#include<bits/stdc++.h>
#define max 1e4+10 
int f[100009],n,m,ans,a,k;
using namespace std;
struct node{
	int be,end,v;
}lu[100009];
bool com(node a,node b)
{
	return a.v>b.v;// Sort from large to small  
}
int find(int x)// Union checking set  
{
	if(x==f[x])
	return x;
	else
	f[x]=find(f[x]);
	return f[x];
}
void kru()
{
	int i,x,y;
	sort(lu+1,lu+m+1,com);// to lu The array is sorted by weight  
	for(i=1;i<=n;i++)
	f[i]=i;// And search set initialization  
	for(i=1;i<=m;i++)
	{
		x=find(lu[i].be);
		y=find(lu[i].end);
		if(x!=y)// No loop formed  
		{
			f[x]=y;
			ans+=lu[i].v;
			a++;
			if(a==k)
			break;
		}
	}
}
int main()
{
	int i;
	cin>>n>>m>>k;
	for(i=1;i<=m;i++)
	{
		cin>>lu[i].be>>lu[i].end>>lu[i].v;
	}
	kru();
	cout<<ans;
	return 0;
}

The sky of the pocket

subject P1195 The sky of the pocket - Luogu | New ecology of computer science education (luogu.com.cn)

Answer key ： The solution is kruskal Algorithm , It is required to be connected K A marshmallow is to ask whether it has been formed K tree .

            Number of connected edges       Number of trees

                n-1            1

                n-2            2

                ....

                 n-k            k

         So judge whether the formed connecting edge is n-k That's it .

The code is as follows ：

#include<bits/stdc++.h>
#define max 1e4+10 
int f[1009],n,m,ans,k,a;
using namespace std;
struct node{
	int be,end,v;
}lu[10009];
bool com(node a,node b)
{
	return a.v<b.v;// Sort from small to large  
}
int find(int x)// Union checking set  
{
	if(x==f[x])
	return x;
	else
	f[x]=find(f[x]);
	return f[x];
}
void kru()
{
	int i,x,y;
	sort(lu+1,lu+m+1,com);// to lu The array is sorted by weight  
	for(i=1;i<=n;i++)
	f[i]=i;// And search set initialization  
	for(i=1;i<=m;i++)
	{
		x=find(lu[i].be);
		y=find(lu[i].end);
		if(x!=y)// No loop formed  
		{
			f[x]=y;
			ans+=lu[i].v;
			a++;
			if(a==n-k)
			break;
		}
	}
}
int main()
{
	int i;
	cin>>n>>m>>k;
	for(i=1;i<=m;i++)
	{
		cin>>lu[i].be>>lu[i].end>>lu[i].v;
	}
	kru();
	if(a==n-k)
	cout<<ans;
	else
	printf("No Answer");
	return 0;
}

Wireless networks

subject P1991 Wireless networks - Luogu | New ecology of computer science education (luogu.com.cn)

Answer key ：     1. What is different from the above question is that the weight of this question is important .

                2. Make it clear that this topic has n tree （ namely m-n side ）

                3. Find the maximum value of all shortest connected edges .

Specific code for weight calculation ：

double jiao(int a,int b)// Find the distance  
{
	int c=d[a].x-d[b].x;
	int k=d[a].y-d[b].y;
	return (double)sqrt((double)c*c+k*k);
}
for(i=1;i<=m;i++)// Find all the ways  
for(j=i+1;j<=m;j++)
{
    ++t; 
	lu[t].be=i;
	lu[t].end=j;
	lu[t].v=jiao(i,j);
}

    The code is as follows ：

#include<bits/stdc++.h>
using namespace std;
int n,m,f[509]; 
struct node1{
	int x,y; 
}d[509*509];
struct node{
	int be,end;
	double v;
}lu[509*509];
double jiao(int a,int b)// Find the distance  
{
	int c=d[a].x-d[b].x;
	int k=d[a].y-d[b].y;
	return (double)sqrt((double)c*c+k*k);
}
bool com(node a,node b)
{
	return a.v<b.v;// Small -> Big sort  
}
int find(int x)
{
	if(x==f[x])
	return x;
	else
	f[x]=find(f[x]);
	return f[x];
}
int main()
{
	cin>>n>>m;
	int i,j,l,g,t=0,cnt=0;
	double ans;
	for(i=1;i<=m;i++)
	cin>>d[i].x>>d[i].y;
	for(i=1;i<=m;i++)
	f[i]=i;// Initialize and query set  
	for(i=1;i<=m;i++)
	for(j=i+1;j<=m;j++)
	{
	++t; 
	lu[t].be=i;
	lu[t].end=j;
	lu[t].v=jiao(i,j);// Find all the ways  
	}
	sort(lu+1,lu+t+1,com);// Sort the roads  
	for(i=1;i<=t;i++)
	{
		l=find(lu[i].be);
		g=find(lu[i].end);
		if(g!=l)// Whether the ring is formed 
		{
			f[l]=g;
			ans=max(lu[i].v,ans);// Find the maximum value of all shortest connected edges 
			cnt++;
			if(cnt==m-n)// formation n tree 
			break;
		}
	}
	printf("%.2lf",ans);
	return 0;
} 

[USACO07DEC]Building Roads S

subject P2872 [USACO07DEC]Building Roads S - Luogu | New ecology of computer science education (luogu.com.cn)

Answer key ：1. This topic is almost the same as the previous one , Ask for your own weight , This topic is more strict about value . To improve the weight function .

double jiao(int a,int b)// Weight calculation 
{
	return (double)(sqrt((double)(d[a].x-d[b].x)*(d[a].x-d[b].x)+(double)(d[a].y-d[b].y)*(d[a].y-d[b].y)));
}

        2. How to deal with connected edges , This problem is simple. Just change the weight of the connected edges to 0 That's it .

        3. Here I wrote it alone lu[] Array assignment statement . The code root is simpler . initialization lu[] Array is called once , It is called once when processing the connected edges , Then the connected edges are assigned twice , After sorting, the first traversal is that the weight of the connected edges is 0 The situation of , At this time, the two points form a connection , Next time, the weight of the connected edge is not 0 situations , Would be j==i The situation of .

        4. The number of connecting edges judged by this topic is n-1, Only one tree has been formed .

The code is as follows ：

#include<bits/stdc++.h>
using namespace std;
const int ax = 1000*1001;
int n,m,f[1009],t;
double ans; 
struct node{
	int x,y;
}d[ax];
struct node1{
	int be,end;
	double v;
}lu[ax];
bool com(node1 a,node1 b)// Sort  
{
	return a.v<b.v;
}
int find(int x)// Looking for my father  
{
	return x==f[x]?x:f[x]=find(f[x]);
}
double jiao(int a,int b)// Weight calculation 
{
	return (double)(sqrt((double)(d[a].x-d[b].x)*(d[a].x-d[b].x)+(double)(d[a].y-d[b].y)*(d[a].y-d[b].y)));
}
void add(int a,int b,double c)
{
	t++;
	lu[t].be=a;
	lu[t].end=b;
	lu[t].v=c;
} 
int main()
{
	cin>>n>>m;
	int i,j,l,g=0;
	for(i=1;i<=n;i++)
	{
	cin>>d[i].x>>d[i].y;
	f[i]=i;// Relationship initialization  
	}
	for(i=1;i<=n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			double z=jiao(i,j);
			add(i,j,z);// Find all the ways  
		}
	}
	for(i=1;i<=m;i++)
	{
	cin>>j>>l;
	add(j,l,0.0);
	}
	sort(lu+1,lu+t+1,com);// Sort  
	for(i=1;i<=t;i++)
	{
		j=find(lu[i].be);
		l=find(lu[i].end);
		if(j!=l)
		{
			ans+=lu[i].v;
			f[j]=l;
			g++;
			if(g==n-1)
			break;
		}
	}
	printf("%.2lf",ans);
	return 0;
}