**prim算法 复杂度O(n^2)
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef long long ll;
#define first x;
#define second y;
typedef pair<int,int> PII;
typedef pair<PII,int> pii;
const int N=510,inf=0x3f3f3f3f,mod=1e9+7;
int g[N][N],n,m,dist[N],pre[N];
bool st[N];
/*
prim算法 复习
1.prim做什么人事呢?
给定一个无向图 在图中选择若干个点将它们连起来边权值和最小,又叫最小生成树
实质:贪心
2.用st数组表示节点是否连通,true 连通
每次我们需要在和那个连通块没连通的一系列点中找到dist最小的那个点
要想找最小肯定得先记录一下
若想输出这个路径 可以用pre数组去记录路径pre[i]=k 表示i->k有一条边
3.找到最近的点且用它去更新其他点到连通块的点;在st数组中把最近点标记为true
int t=-1; for(int j=1;j<=n;j++)
if(!st[j]&&(t==-1||dist[j]<dist[t]))
t=j;
更新:
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],g[t][j]);
st[t]=true;
点数n=500 边数 m=100000
m>n*logn 100000>500*9
图为稠密图用邻接矩阵g
*/
int prim()
{
memset(dist,0x3f,sizeof dist);
int res=0;
dist[1]=0;
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
if(!st[j]&&(t==-1||dist[j]<dist[t]))
t=j;
st[t]=true;
/* if(dist[t]==inf&&i)
return inf;
if(i)*/
res+=dist[t];
for(int j=1;j<=n;j++)
// dist[j]=min(dist[j],g[t][j]);
if(dist[j]>g[t][j]&&!st[i])
dist[j]=g[t][j],pre[j]=t;
}
return res;
}
void getPath()//输出各个边
{
for(int i = n; i > 1; i--)//n 个节点,所以有 n-1 条边。
{
cout << i <<" " << pre[i] << " "<< endl;// i 是节点编号,pre[i] 是 i 节点的前驱节点。他们构成一条边。
}
}
int main()
{
memset(g,0x3f,sizeof g);
cin>>n>>m;
while(m--)
{ int a,b,w;
cin>>a>>b>>w;
g[a][b] = g[b][a] = min(g[a][b],w);
}
int res=prim();
/* if(res==inf)
puts("impossible");
else
cout<<res<<endl;*/
getPath();
return 0;
}
kruskal算法
复杂度mlogm
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef long long ll;
#define x first
#define y second
#define _for(i,a,b) for( int i=(a); i<(b); ++i)
typedef pair<int,int> PII;
typedef pair<PII,int> pii;
const int N=200010,M=100010,inf=0x3f3f3f3f,mod=1e9+7;
int p[M];
int n,m;
/*
* kruskal 算法:
* 1. 用结构体记录 两个点之间的这条边 和权值w,用sort排序由w从小到大
* 2. 并查集:find函数找根节点
* <1> 在主函数的初始化 每个点的父节点是它本身brand p[i]=i;
* <2> 函数 若x!=p[x] 即这个点本身的父节点不是它自己的时候
* qu寻找p[x]的父节点这个其实死循环(但由最后一个节点end)
* 用代码表示p[p[p[...x...]]]
*3. cnt:记录连接了多少个点
* 由抽屉原理 n个点无向图最多存在n-1条边
* 若cnt<n-1 表面我们这个图出现了环则impossibe
*/
struct Edge
{
int a,b,w;
bool operator<(const Edge &W) const
{
return w<W.w;
}
}edges[N];
int find(int x) //并查集找根节点
{
if(p[x]!=x)
p[x]= find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
_for(i,0,m)
{
int a, b, w;
cin >> a >> b >> w;
edges[i] = {a, b, w};
}
_for(i,0,n)
p[i]=i;
sort(edges,edges+m);
int cnt=0,res=0;
_for(i,0,m)
{
int a=edges[i].a,b=edges[i].b,w=edges[i].w;
a= find(a),b= find(b);
if(a!=b)
p[a]=b,cnt++,res+=w;
}
if(cnt<n-1)
puts("impossible");
else
cout<<res<<endl;
return 0;
}**