最小生成树是一种常见的图论问题,具体表现为
给以一张图,请你在保证他连通的情况下,使他所有边权之和最小。
对于这一类问题有两种解决方法,第一种为 K r u s k a l Kruskal Kruskal 第二种为 P r i m Prim Prim。两种算法各有各自的优势, K r u s k a l Kruskal Kruskal 时间复杂度为 m l o g m m log m mlogm, P r i m Prim Prim 则为 n 2 n^2 n2 不同情况下应采用不同的方案。
原理
两种算法本质上都是贪心,只是 K r u s k a l Kruskal Kruskal 以边为本, P r i m Prim Prim 则以点为本。
K r u s k a l Kruskal Kruskal 首先对所有的边按照权值从小到大排序,排序之后遍历所有的边,每次检查这条边的两个端点是否连通(并查集),如果不连通直接连通即可(排序了),连通则跳过。可以证明这个方案是合法且最优的。
P r i m Prim Prim 大家都认为和迪杰斯特拉很像,都是每次找到最小的点,然后从那个点找点连,可以使用优先队列维护,降低时间复杂度。
Code
K u r u s k a l Kuruskal Kuruskal
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define R register int
using namespace std;int k,n,m,cnt,sum,ai,bi,ci,head[5005],dis[5005],vis[5005];struct Edge
{int v,w,next;
}e[400005];void add(int u,int v,int w)
{e[++k].v=v;e[k].w=w;e[k].next=head[u];head[u]=k;
}typedef pair <int,int> pii;
priority_queue <pii,vector<pii>,greater<pii> > q;void prim()
{dis[1]=0;q.push(make_pair(0,1));while(!q.empty()&&cnt<n){int d=q.top().first,u=q.top().second;q.pop();if(vis[u]) continue;cnt++;sum+=d;vis[u]=1;for(R i=head[u];i!=-1;i=e[i].next)if(e[i].w<dis[e[i].v])dis[e[i].v]=e[i].w,q.push(make_pair(dis[e[i].v],e[i].v));}
}
int main()
{memset(dis,127,sizeof(dis));memset(head,-1,sizeof(head));scanf("%d%d",&n,&m);for(R i=1;i<=m;i++){scanf("%d%d%d",&ai,&bi,&ci);add(ai,bi,ci);add(bi,ai,ci);}prim();if (cnt==n)printf("%d",sum);else printf("orz");
}
P r i m Prim Prim
#include<bits/stdc++.h>
using namespace std;
int k,n,m;
int cnt,sum,dis[10005],vis[10005];
vector <int> E[200005];
vector <int> W[200005];
void add(int u,int v,int w)
{E[u].push_back(v);W[u].push_back(w);
}
priority_queue <pair <int,int>,vector<pair <int,int> >,greater<pair <int,int> > > q;
void prim()
{memset(dis,127,sizeof(dis));dis[1]=0;q.push(make_pair(dis[1],1));while(!q.empty()&&cnt<n){int d=q.top().first,u=q.top().second;q.pop();if(vis[u]) continue;cnt++;sum+=d;//有就加vis[u]=1;for(int i=0; i<E[u].size(); i++)if(W[u][i]<dis[E[u][i]]){dis[E[u][i]]=W[u][i];q.push(make_pair(dis[E[u][i]],E[u][i]));}}
}
int a,b,c;
int main()
{scanf("%d%d",&n,&m);for(int i=1; i<=m; i++){scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}prim();if(cnt==n)printf("%d",sum);else printf("orz");
}