网站做统计分析/中山网站seo

最小生成树

①Kruskal：sort()排序、并查集、最小生成树的性质（一张图中有n个结点，则n个结点的最小生成树中只有n-1条边）、边集数组。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 2e5+5;
struct edge{int u,v,w;
}e[maxn];
int f[maxn] = {0};
int findf(int x){if(x == f[x])	return x;return f[x] = findf(f[x]);
}
int n,m,res = 0;
inline bool cmp(const edge &e1,const edge &e2){return e1.w < e2.w;
}
bool Kruskal(){sort(e+1,e+1+m,cmp);int cnt = 0;for(int i=1;i<=m;i++){int eu = findf(e[i].u),ev = findf(e[i].v);if(eu == ev)	continue;f[eu] = ev;res += e[i].w;if(++cnt == n-1)	return true;//找到了能够构成最小生成树的n-1条边。 }
//	cout<<"orz";//不连通则输出orz。 return false;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){f[i] = i;}for(int i=1;i<=m;i++){cin>>e[i].u>>e[i].v>>e[i].w;}if(Kruskal())cout<<res;else{cout<<"orz";}return 0;
}

②堆优化的Prim：https://www.luogu.com.cn/problem/solution/P3366
原答主：https://www.luogu.com.cn/user/51313

#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");
}