最小生成ツリー---クルースカル(Kruskal)アルゴリズム

最小生成ツリーを解決するprimとkruskalの2つのアルゴリズムがあることが知られていた.
2つのアルゴリズムは対象の問題が非常に異なるようで、システムはこの2つのアルゴリズムを解決します
注意:primアルゴリズムは稠密図に適しており、その時間複雑度はO(n^2)であり、その時間複雑度はエッジの数に関係なく、kruskalアルゴリズムの時間複雑度はO(eloge)がエッジの数に関係し、疎図に適している.
図の辺数がeである場合,Kruskalアルゴリズムに要する時間はO(eloge)である.e=Ω(n^2)の場合、KruskalアルゴリズムはPrimアルゴリズムより劣る.しかし,e＝o(n^2)の場合,KruskalアルゴリズムはPrimアルゴリズムよりもはるかに優れていた.
kruskal----集計エッジ;prim----集計点
詳細を調べます.https://blog.csdn.net/dellaserss/article/details/7724401
1.kruskal(+およびセット)
mark:https://www.cnblogs.com/yoke/p/6697013.html
裸のテンプレートの問題:hdu 1232

#include
using namespace std;
#define maxn 1000+10
//Accepted
//Time ：31ms
//Memory ：1384kB
//Length ：668
//Lang ：G++ 
int father[maxn];
void init(int n)//    
{
	for(int i=1;i<=n;i++)
	{
		father[i]=i;
	}
}
int find(int x)//  
{
	return x==father[x]?x:father[x]=find(father[x]);
 } 
 
void combine(int a,int b)//  
{
	int fa=find(a);
	int fb=find(b);
	if(fa!=fb)
	{
		father[fa]=fb;
	}
 } 
int main()
{
	int n,m,u,v;
	long long ans=0;
	while(scanf("%d",&n)&&n)
	{
		init(n);
		ans=0;
		scanf("%d",&m);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&u,&v);
			combine(u,v);//   
		}
		for(int i=1;i<=n;i++) 
		{
			if(father[i]==i)
			ans++;//              
		}
		printf("%lld
",ans-1);//ans-1             
	}
	return 0;
}

hdu 4314
k個のつながっている点の間の線を切除すると、k個の点の最小生成ツリーに変換されます.
二つのケース
1.両方の点が危険点である場合削除するには重み値を計算するに変換
2.一方が危険点である一方ではなく、2つの点を併合する親ノードの危険点の外側、すなわちその親ノードが新しい木の親ノードである
//これで今度また危険な点に遭遇したら削除できます!get思想みたい

#include
#define maxn 100000+10
using namespace std; 
int flag[maxn];
int fa[maxn];
int t,k,n; 
void unit(int n)//    
{
	for(int i=0;ib.w;//     
 } 
 
void kruskal()
{
	long long ans=0;
	sort(e,e+n-1,cmp);
	
	//   
	unit(n);
	//     
	for(int i=0;i

poj 1251
テンプレートの問題は何も説明できません
スペースを避けるために入力したのでcinを使いましょう.そして突然注意しました.いろいろな入力の特徴をまとめてみます.他の人のブログを振り返ってみましょう.

#include
#include 
#include
#define maxn 1000
using namespace std;
int father[30]; 

struct ed
{
	int u,v,w;
}point[maxn];//   ，re   55555555         

bool cmp(ed a,ed b)
{
	return a.w>ch>>time;
			//int us= 
			for(int i=count;i>sh>>wl;
				getchar();
				point[i].u=ch-'A';
				point[i].v=sh-'A';
				point[i].w=wl;
			}
			q++;
			count+=time;
		}
		//kruskal
		int ans=0;
		sort(point,point+count,cmp);
		for(int i=0;i

poj 1287

//Accepted
//16ms	0.7mb	

#include
#include 
#include
using namespace std;
#define maxn 10000
int father[60];
struct node
{
	int u,v,w;
}ed[maxn];
bool cmp(node a,node b)
{
	return a.w>n&&n)
 	{
 		init(n);
 		cin>>m;
 		for(int i=1;i<=m;i++)
 		{
 			scanf("%d %d %d",&ed[i].u,&ed[i].v,&ed[i].w);
		 }
		 //
		 sort(ed+1,ed+m+1,cmp);
		 int ans=0;
		 for(int i=1;i<=m;i++)
		 {
		 	if(find(ed[i].u)!=find(ed[i].v))
		 	{
		 		ans+=ed[i].w;
				 combine(ed[i].u,ed[i].v); 
			 } 
		 }
		 cout<

poj 2031
数学の公式に注意して、もしもし、QQを泣きました

#include
#include
#include
#include
//Accepted
//32ms
//0.4mb
int father[1000];
using namespace std;
struct node
{
	int p;
	double x,y,z,r;
}ed[1000];

struct node2
{
	int u,v;
	double w;
}ed2[1000000];
bool cmp(node2 a,node2 b)
{
	return a.w>n&&n)
	{
	   init(n);
	   for(int i=1;i<=n;i++)
		{
			ed[i].p=i;
			scanf("%lf %lf %lf %lf",&ed[i].x,&ed[i].y,&ed[i].z,&ed[i].r);
		}
		int t=1;
		for(int i=1;i

poj  2421

//Accepted
//Time 47ms
//Memory 240kB
#include
#include
#include
#define maxn 10000+10
using namespace std;
int father[110];
int dis[110][110];
struct node
{
	int u,v,w;	
}ed[maxn];

void init(int n)
{
	for(int i=1;i<=n;i++)
	{
		father[i]=i;
	}
}

int find(int x)
{
	return x==father[x]?x:father[x]=find(father[x]); 
}

bool cmp(node a,node b)
{
	return a.w>n;
	init(n);
	int t=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int p;
			scanf("%d",&p);
			if(j>i)
			{
				ed[++t].u=i;
				ed[t].v=j;
				ed[t].w=p;
				
			}
		}
	}
	//
	long long ans=0;
	sort(ed+1,ed+t+1,cmp);
	cin>>q;
	while(q--)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		combine(a,b);
	}
	for(int i=1;i<=t;i++)
	{
		if(find(ed[i].u)!=find(ed[i].v))
		{
			combine(ed[i].u,ed[i].v);
			ans+=ed[i].w;
		}
	}
	printf("%lld",ans);
}

zoj 1586 
パスの長さに両端の重みを付ける

#include
#include
#include
#define maxn 1000000+10
using namespace std;
int father[1010];
int prd[1010];
struct node
{
	int u,v,w;	
}ed[maxn];

void init(int n)
{
	for(int i=1;i<=n;i++)
	{
		father[i]=i;
	}
}

int find(int x)
{
	return x==father[x]?x:father[x]=find(father[x]); 
}

bool cmp(node a,node b)
{
	return a.w>t;
	while(t--)
	{
		cin>>n;
	init(n);
	int t=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&prd[i]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int p;
			scanf("%d",&p);
			if(j>i)
			{
				ed[++t].u=i;
				ed[t].v=j;
				ed[t].w=p+prd[ed[t].u]+prd[ed[t].v];
				
			}
		}
	}
	//
	long long ans=0;
	sort(ed+1,ed+t+1,cmp);
	for(int i=1;i<=t;i++)
	{
		if(find(ed[i].u)!=find(ed[i].v))
		{
			combine(ed[i].u,ed[i].v);
			ans+=ed[i].w;
		}
	}
	printf("%lld
",ans);
	}
	
}