6

xyf LV 5 @ 2021-9-14 20:38:38

使用 Kruskal 算法解决。

主要思路：把边以边权从小到大排序。接下来从头开始枚举边。如果边会使得后面的图一定不是树（即出现环），则跳过。如果总共已经 $n-1$ 条边，则结束。如果所有枚举完后不到 $n-1$ 条边，则返回不行（此题没有）。

那么如何判断是否有环？最好的方法就是使用优化的并查集。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int m,n,cnt,sum;
int fa[100009];
struct edge{
    int w;
    int u,v;
};
edge e[200009];
bool cmp(edge x,edge y){
    return x.w<y.w;
}
void init(){
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
    for(int i=1;i<=n;i++) fa[i]=i;
}
int anc(int k){
    if(fa[k]==k) return k;
    else return fa[k]=anc(fa[k]);
}
void relate(int x,int y){
    if(x<y) swap(x,y);
    fa[anc(y)]=anc(x);
}
signed main(){
    init();
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++){
        if(anc(e[i].u)!=anc(e[i].v)){
            cnt++;
            relate(e[i].u,e[i].v);
            sum+=e[i].w;
        }
        if(cnt==n-1) break;
    }
    if(cnt!=n-1) cout<<"No solution";
    else cout<<sum;
    return 0;
}

3

Higanbana LV 3 @ 2022-7-19 17:57:50

这里讲解一下 $Kruskal$ 算法。

$Kruskal$ 的主要思想：贪心。

既然我要求的是最小权值，那么我对所有边进行排序，然后一条一条看就行了。

那么怎么样的边是可选的呢？

很显然，如果一边上两个点（未连接时）在两个连通分量中，那么这条边是可选的（毕竟不连白不连）；而如果这两点在一个连通分量中，那么这条边就不可选了。

最后，因为树的权值最小，当边数为 $n-1$ 时，程序结束。

注意权值数据范围。

代码如下：

#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int n,m,s,cnt=1,fa[maxn];
struct Edge{
    int u,v,w;
} e[maxn];
int find(int k){
    if(fa[k]==k)return k;
    return fa[k]=find(fa[k]);
}
bool cmp(Edge a,Edge b){
    return a.w<b.w;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
        cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m&&cnt<n;i++){
        int u=e[i].u,v=e[i].v;
        if(find(u)==find(v))continue;
        s+=e[i].w;
        cnt++;
        fa[find(u)]=find(v);
    }if(cnt<n)cout<<-1;
    else cout<<s;
    return 0;
}

2

xiaoququ LV 7 @ 2022-11-11 19:39:56

怎么都不约而同地使用 Kruskal 去了，堆优化的 Prim 也可以通过这一题的。

Prim 算法是什么 & 算法原理

Prim 算法与最短路中的 Dijsktra 算法有点相像。我们随便选取一个根，接下来从根节点向外贪心地选取最小的边，将其加入至最小生成树中即可，其中，选取最小的边的操作可以用堆优化至 $O(\log n)$ 。

总的复杂度： $O(n\log n)$ 。

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

const int MAXN = 1e5 + 5;
struct _node {
    int v, w;
    bool operator < (const _node b) const {
        return w > b.w;
    }
};
vector<_node> G[MAXN];
int n, m, dis[MAXN];
bool vis[MAXN];

int prim() {
    int cnt = 0, ret = 0;
    memset(dis, 0x3f, sizeof dis);
    priority_queue<_node> pq;
    pq.push({1, 0});
    while (pq.size() && cnt < n) {
        auto [u, w] = pq.top(); pq.pop();
        if (vis[u]) continue;
        cnt++; ret += w;
        vis[u] = true;
        for (auto [v, x]:G[u]) {
            if (x < dis[v]) {
                dis[v] = x;
                pq.push({v, dis[v]});
            }
        }
    }
    return ret;
}

signed main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    cout << prim() << endl;
    return 0;
}

2

pengzijun LV 6 @ 2022-2-19 13:30:24

使用 Kruskal 解决。

Kruskal 使用的是一个贪心算法，首先把边权按从小到大排序，然后依次加边，如果加出了环，那就不加了。如果有 $n-1$ 条边那么就已经得出答案。

证明：如果有一条边 $u$ 删除后可以用其他边 $v$ 顶替，根据排序方法可知 $u\le v$ ，也就是说，换上 $v$ 之后不能使答案变优。

注意最终答案最大可以在 $10^11$ 的级别，需要开 long long。

代码瓶颈在排序，时间复杂度 $O(m\log m)$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
int father[maxn],m,n,u,v,w,ans;
struct edge{
	int x,y,z;
	bool operator <(const edge &a) const{
		return z<a.z;
	}
};
vector<edge> G;
void makeSet(int n){
	for(int i=1;i<=n;i++)
		father[i]=i;
}
int findSet(int x){
	if(father[x]==x)
		return x;
	return father[x]=findSet(father[x]);
}
void Kruskal(){
	makeSet(n);
	sort(G.begin(),G.end());
	int edgeNum=0;
	for(int i=0;i<m;i++){
		int x=findSet(G[i].x),y=findSet(G[i].y);
		if(x!=y){
			father[x]=y;
			ans+=G[i].z;
			edgeNum++;
		}
		if(edgeNum==n-1)
			return;
	}
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		G.push_back(edge({u,v,w}));
	}
    Kruskal();
	printf("%lld\n",ans);
	return 0;
}

1

xiaobeng LV 9 @ 2024-6-1 18:33:12

在这里，我使用了 Kruskal 算法解决这道题（想看Prim算法的移步别的题解）。

思路：把边从边权大小从小到大排序，从 $0$ 号开始遍历整个图，创建最小生成树，累加权值。使用一个优化后的并查集，如果所有边都在一个集中，则结束。输出权值总和。如果枚举完所有的点后仍达不到 $n-1$ 条，则不行。

最后，我想提醒大家：

不开longlong,见！祖！宗！

代码（禁止抄袭！）：

#include<bits/stdc++.h>
using namespace std;
int n,m,sum,cnt,f[200001];
struct node{
	int u,v,w;
}a[200001];
bool cmp(node x,node y){
	return x.w<y.w;
}
int find(int x){
	if(f[x]==x){
		return x;
	}
	return f[x]=find(f[x]);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
	}
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++){
		if(find(a[i].u)!=find(a[i].v)){
			cnt++;
			sum+=a[i].w;
			f[find(a[i].u)]=find(a[i].v);
		}
	}
	if(cnt!=n-1){
		printf("orz");
		return 0;
	}
	printf("%d",sum);
	return 0;
}

1

AVstarFXJ LV 2 @ 2023-11-16 15:53:45

最小生成树个人喜欢 $Kruskal$ 算法

前置知识：贪心，并查集

原理

最小生成树：一个无向连通图，边权值和最小的生成树

既然是边权值和最小，那么我们可以用贪心的思想，将边权从小到大排序，依次插入最小生成树中。

这是具体的排序后插入的操作：

如果 $u$ ， $v$ 两点之间没有路径，我们就将这条边加入到最小生成树中；
如果 $u$ ， $v$ 两点之间已经在最小生成树中有路径，或者形成了一个环，那么我们就把这条边"扔掉"。

重复以上步骤，我们可以顺便统计最小生成树的边权和，直到最小生成树中有 $n-1$ 条边(也就是构成了一棵树)。

至于实现有无路径，我们可以使用并查集实现。

这样子的时间复杂度最优是 $O(m \log{m})$

注意!!! 开long long!!!， $0 \le w_i \le 10^6$ !!!

这里提一嘴另一种求解最小生成树的方式:Prim，题解(link)可以参考楼下的 xiaoququ 大佬。

它与 $Kruskal$ 的区别就在于一个是加点(Prim)，一个是加边(Kruskal)，而且 Prim 类似于最短路中的 Dijsktra 算法。

AC code

// Kruskal
const int N = 2e5 + 5;
typedef long long ll;

struct Edge{
	ll u, v, w;
}e[N];

bool cmp(Edge x, Edge y){
	return x.w < y.w;
}

int find(int x){
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}

int main(){

	sort (e + 1, e + m + 1, cmp);
	ll cnt = 0;
	int tot = 0;
	for (int i = 1; i <= m; ++i){
		int u = e[i].u, v = e[i].v, w = e[i].w;
		int fu = find(u), fv = find(v);
		
		if (fv == fu) continue;
		fa[fu] = fv;
		tot++;
		cnt += w;
		if (tot == n - 1) break;
	}
	return 0;
}

-1

王靖翔 LV 6 @ 2023-9-15 21:12:34

本题目可以用最小生成树之 Kruskal 算法解

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int M = 2e5 + 10;
int fa[N], n, m;
long long ret; // 不开 long long 见祖宗
struct node {
	int x, y, z;
}e[M];

bool cmp(node n1, node n2) {
	return n1.z < n2.z;
}
void INIT() { // 初始化每个节点的父节点都是自己
	for (int i = 1; i <= n; i++) {
		fa[i] = i; // 相当于一个图有 n 个节点，也有 n 个联通块
	} // 可以说是一个图没有边，初始化，Kruskal 的基本思想就是贪心
} 
int dfs(int x) { // 并查集，不懂看后面
	return fa[x] == x ? x : fa[x] = dfs(fa[x]);
    // fa[x] = dfs(fa[x]) 是一个路径压缩
}
void kruskal() {
	int cnt = 0;
	sort(e+1, e+m+1, cmp); // 排序所有的边
	for (int i = 1; i <= m; i++) { // 枚举所有的边
		int fx = dfs(e[i].x); // find
		int fy = dfs(e[i].y);
		if (fx != fy) { // 可以通过并查集函数来理解
			fa[fx] = fy; //
			ret += e[i].z;
			cnt++; // 这个没有用，但是这个可以计数是否可以构成最小生成树
		}
	}
	cout << ret;
}

int main() {
    cin >> n >> m;
	INIT();
    for (int i = 1; i <= m; i++) {
    	scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z);
	}
	kruskal();
    return 0;
}

并查集

-1

龚子恒 LV 4 @ 2023-8-10 12:54:55

#include<bits/stdc++.h>
using namespace std;
#define int long long
int m,n,cnt,sum;
int fa[100009];
struct edge{
    int w;
    int u,v;
};
edge e[200009];
bool cmp(edge x,edge y){
    return x.w<y.w;
}
void init(){
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
    for(int i=1;i<=n;i++) fa[i]=i;
}
int anc(int k){
    if(fa[k]==k) return k;
    else return fa[k]=anc(fa[k]);
}
void relate(int x,int y){
    if(x<y) swap(x,y);
    fa[anc(y)]=anc(x);
}
signed main(){
    init();
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++){
        if(anc(e[i].u)!=anc(e[i].v)){
            cnt++;
            relate(e[i].u,e[i].v);
            sum+=e[i].w;
        }
        if(cnt==n-1) break;
    }
    if(cnt!=n-1) cout<<"No solution";
    else cout<<sum;
    return 0;
}

-1

Leo2 LV 10 @ 2023-3-25 9:36:19

#include<bits/stdc++.h>
using namespace std;
#define int long long
int m,n,cnt,sum;
int fa[100009];
struct edge{
int w;
int u,v;
};
edge e[200009];
bool cmp(edge x,edge y){
return x.w<y.w;
}
void init(){
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
for(int i=1;i<=n;i++) fa[i]=i;
}
int anc(int k){
if(fa[k]==k) return k;
else return fa[k]=anc(fa[k]);
}
void relate(int x,int y){
if(x<y) swap(x,y);
fa[anc(y)]=anc(x);
}
signed main(){
init();
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++){
if(anc(e[i].u)!=anc(e[i].v)){
cnt++;
relate(e[i].u,e[i].v);
sum+=e[i].w;
}
if(cnt==n-1) break;
}
if(cnt!=n-1) cout<<"No solution";
else cout<<sum;
return 0;
}

-1

YHS__114514 LV 6 @ 2022-8-18 17:05:49

$Kruskal$ 解决问题， $ans$ 注意开 $long long$ ,不然会爆

下面是 $AC$ 代码：

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    bool flag=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            flag=0;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return (flag?x:~(x-1));
}
int n,m,k;
long long ans=0;
int f[100001];
struct edge
{
	int x,y,z;
}a[200001];
inline void init()
{
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
	}
}
inline int find(int x)
{
	return x==f[x]?x:f[x]=find(f[x]);
}
inline bool cmp(edge a,edge b)
{
    return a.z<b.z;
}
int main()
{
	n=read();m=read();
	init();
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		a[i].x=read();a[i].y=read();a[i].z=read();
	}
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int fx=find(a[i].x),fy=find(a[i].y);
		if(fx==fy)
		{
			continue;
		}
		f[fx]=fy;
		ans+=a[i].z;	
	}
	cout<<ans;
	return 0;
}

完结撒花！

-2

Leo2 LV 10 @ 2023-3-23 20:11:34

#include<bits/stdc++.h>
using namespace std;
#define int long long
int m,n,cnt,sum;
int fa[100009];
struct edge{
    int w;
    int u,v;
};
edge e[200009];
bool cmp(edge x,edge y){
    return x.w<y.w;
}
void init(){
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
    for(int i=1;i<=n;i++) fa[i]=i;
}
int anc(int k){
    if(fa[k]==k) return k;
    else return fa[k]=anc(fa[k]);
}
void relate(int x,int y){
    if(x<y) swap(x,y);
    fa[anc(y)]=anc(x);
}
signed main(){
    init();
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++){
        if(anc(e[i].u)!=anc(e[i].v)){
            cnt++;
            relate(e[i].u,e[i].v);
            sum+=e[i].w;
        }
        if(cnt==n-1) break;
    }
    if(cnt!=n-1) cout<<"No solution";
    else cout<<sum;
    return 0;
}

-2

joy2010WonderMaker LV 5 @ 2022-3-16 16:25:22

使用 Kruskal 算法。

有环的情况可以用并查集跳过。

#include<bits/stdc++.h>
using namespace std;
long long n,m,fa[100005],cnt,ans,s[100005];
struct node{
	long long u,v,w;
}a[200005];
bool cmp(node x,node y){
	return x.w<y.w;
}
int find(int x){
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	if(s[x]<s[y])
		swap(x,y);
	int fx=find(x),fy=find(y);
	fa[fy]=fx,s[fx]+=s[fy];
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%lld%lld%lld",&a[i].u,&a[i].v,&a[i].w);
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++){
		if(find(a[i].u)==find(a[i].v))
			continue;
		merge(a[i].u,a[i].v);
		cnt++;
		ans+=a[i].w;
		if(cnt==n-1)
			break;
	}
	printf("%lld",ans);
	return 0;
}

-4

龚子恒 LV 4 @ 2023-8-10 12:55:33

#include<bits/stdc++.h> using namespace std; #define int long long int m,n,cnt,sum; int fa[100009]; struct edge{ int w; int u,v; }; edge e[200009]; bool cmp(edge x,edge y){ return x.w<y.w; } void init(){ cin>>n>>m; for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w; for(int i=1;i<=n;i++) fa[i]=i; } int anc(int k){ if(fa[k]k) return k; else return fa[k]=anc(fa[k]); } void relate(int x,int y){ if(x<y) swap(x,y); fa[anc(y)]=anc(x); } signed main(){ init(); sort(e+1,e+m+1,cmp); for(int i=1;i<=m;i++){ if(anc(e[i].u)!=anc(e[i].v)){ cnt++; relate(e[i].u,e[i].v); sum+=e[i].w; } if(cntn-1) break; } if(cnt!=n-1) cout<<"No solution"; else cout<<sum; return 0; }

-5

Rratic LV 5 @ 2021-5-17 22:34:16

注意：

不要把洛谷AC代码移过来，注意数据范围
不要用int！！

不要复制下面的代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct Edge{
int u,v;
long long len;
}e[2000₁0];

bool cmp(Edge a,Edge b){
return a.len<=b.len;
}
int fa[100010];
void init(){
for(int i=1;i<=n;i++)fa[i]=i;
}
int get(int x){
if(fa[x]==x)return x;
return fa[x]=get(fa[x]);
}
void merge(int x,int y){
x=get(x);
y=get(y);
if(x!=y){
fa[x]=y;
}
}
int kruskal(int n,int m){
long long sum=0;
init();
sort(e,e+m,cmp);
for(int i=0;i<m;i++){
int fu=get(e[i].u);
int fv=get(e[i].v);
if(fu!=fv){
fa[fv]=fu;
sum+=e[i].len;
}
}
return sum;
}
int mian(){
cin>>n>>m;
for(int i=0;i<m;++i)cin>>e[i].u>>e[i].v>>e[i].len;
cout<<kruskal(n,m)<<endl;
return 0;
}

14 条题解

Prim 算法是什么 & 算法原理

不开longlong,见！祖！宗！

原理

AC code

【模板】最小生成树

信息

状态

开发

支持

14 条题解

Prim 算法是什么 & 算法原理

不开longlong,见！祖！宗！

原理

AC code

【模板】最小生成树

信息

状态

开发

支持

还没有账户？

登录