最小生成树
无向图 连通图才有最小生成树 可以判断图是否连通
记住思路 不要死记模板 灵活建图写代码
Prim算法
由Prim提出。该算法的基本思想是从一个结点开始，不断加点（而不是 Kruskal 算法的加边）。每次总是选出一个离生成树距离最小的点去加入生成树，最后实现最小生成树。类似Dijkstra算法。时间复杂度 O（V^2）------->稠密图
模板
#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
const int inf=0x7fffffff;
int cnt;
struct edge
{
int u,w,next;
}e[2*maxn];
int head[maxn];
int dis[maxn];
bool vis[maxn];
int n,m;
void add(int x,int y,int w) //链式前向星的加点方法
{
cnt++;
e[cnt].u=y;
e[cnt].w=w;
e[cnt].next=head[x];
head[x]=cnt;
}
int prim()
{
for(int i=1;i<=n;i++)dis[i]=inf;
dis[1]=0;
vis[1]=1;
int now=1;
for(int i=head[now];i;i=e[i].next) //链式前向星的遍历方法 可利用堆优化
{
int u=e[i].u;
dis[u]=min(dis[u],e[i].w);
}
int tot=0;
int sum=0;
while(tot<n-1)
{
int mindis=inf;
for(int i=1;i<=n;i++)
{
if(!vis[i]&&dis[i]<mindis)
{
now=i;
mindis=dis[i];
}
}
if(mindis==inf)return -1;//图不连通
tot++;
sum+=mindis;
vis[now]=1;
for(int i=head[now];i;i=e[i].next) //链式前=前向星的遍历方法
{
int u=e[i].u;
if(vis[u])continue;
dis[u]=min(dis[u],e[i].w);
}
}
return sum;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
int ans=prim();
if(ans==-1)printf("orz");
else printf("%d",ans);
}
例题
只能用Prim算法 边有5000*5000
完全图不用存图
设置变量不要用y1,y2,y3…
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define INF 1e9
int n;
struct node{
int x,y;
}p[5005];
double dis[5005];
int v[5005];
double cal(const node& p1,const node& p2){
return (double)sqrt((double)(p1.x-p2.x)*(p1.x-p2.x)+(double)(p1.y-p2.y)*(p1.y-p2.y));//用double
}
int main(){
cin>>n;
for(int i=1;i<=n;++i){
cin>>p[i].x>>p[i].y;
}
dis[1]=0;
v[1]=1;
for(int i=2;i<=n;i++){
dis[i]=cal(p[1],p[i]);
}
double minn=INF,ans=0;
int k;
for(int i=1;i<n;++i){
minn=INF;
k=-1;
for(int j=1;j<=n;++j){
if(v[j]==0&&dis[j]<minn){
k=j;
minn=dis[j];
}
}
v[k]=1;
ans+=minn;
for(int j=1;j<=n;++j){
if(v[j]==0&&dis[j]>cal(p[k],p[j])){
dis[j]=cal(p[k],p[j]);
}
}
}
printf("%.2lf\n",ans);
return 0;
}
Kruskal算法
Kruskal 算法：由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。在加入边时，需要通过 并查集 来判断该边的两个端点是否属于同一集合（树），避免形成 “环”。时间复杂度 O（ElogE）-----> 稀疏图
模板
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include <climits>
#include<utility>
using namespace std;
const int maxn = 110; // 最大顶点数
const int maxm = 10010; // 最大边数
struct Edge {// 使用结构体储存每一条边，便于排序
int u, v, w; // 表示有一条 (u,v) 的无向边，边权为 w
} e[maxm+5];
int ecnt;// 用于边表计数
void addEdge(int u, int v, int w){ // 加入一条无向边
++ecnt;
e[ecnt].u = u;
e[ecnt].v = v;
e[ecnt].w = w;
}
int fa[maxn]; // 并查集相关
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]); // 路径压缩
}
int n,m; // 顶点数 边数
bool cmp(const Edge &a, const Edge &b){
return a.w < b.w;
}
int Kruskal() { // Kruskal 算法核心过程
for (int i = 1; i <= n; i++) {
fa[i] = i; // 初始化并查集
}
sort (e + 1, e + ecnt + 1, cmp);
int sum = 0;
for (int i = 1; i <= ecnt; i++) {
int u = e[i].u;
int v = e[i].v;
u = find(u);
v = find(v);
if (u != v) {
fa[u] = v;
sum += e[i].w;
}
}
return sum;
}
int main(){
scanf("%d %d",&n,&m);
int x,y,w;
for (int i = 1; i <= m; i++) {
scanf("%d %d %d", &x,&y,&w);
addEdge(x, y, w);
}
int ans = Kruskal();
printf("%d\n",ans);
return 0;
}
例题
引入虚假的点来转化点权
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int a,b;
struct Edge{
int u,v,w;
}e[300000];
int fa[505];
int cnt;
bool cmp(const Edge& x,const Edge& y){
return x.w<y.w;
}
int find(int x){
if(x!=fa[x]) return fa[x]=find(fa[x]);
return fa[x];
}
int main(){
cin>>a>>b;
//引入虚假的物品0，买了0再买其他物品
for(int i=1;i<=b;++i){
e[++cnt].u=0;
e[cnt].v=i;
e[cnt].w=a;
}
int k;
for(int i=1;i<=b;++i){
for(int j=1;j<=b;++j){
cin>>k;
if(k!=0){
e[++cnt].u=i;
e[cnt].v=j;
e[cnt].w=k;
}
}
}
sort(e+1,e+cnt+1,cmp);
for(int i=0;i<=b;++i){
fa[i]=i;
}
int x,y,fx,fy,ans=0;
for(int i=1;i<=cnt;++i){
x=e[i].u;
y=e[i].v;
fx=find(x);
fy=find(y);
if(fx!=fy){
ans+=e[i].w;
fa[fx]=fy;
}
}
cout<<ans<<endl;
return 0;
}