14 solutions

  • 6
    @ 2021-9-14 20:38:38

    使用 Kruskal 算法解决。

    主要思路:把边以边权从小到大排序。接下来从头开始枚举边。如果边会使得后面的图一定不是树(即出现环),则跳过。如果总共已经 n1n-1 条边,则结束。如果所有枚举完后不到 n1n-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
      @ 2022-7-19 17:57:50

      这里讲解一下 KruskalKruskal算法。

      KruskalKruskal的主要思想:贪心。

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

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

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

      最后,因为树的权值最小,当边数为 n1n-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
        @ 2022-11-11 19:39:56

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

        Prim 算法是什么 & 算法原理

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

        总的复杂度:O(nlogn)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
          @ 2022-2-19 13:30:24

          使用 Kruskal 解决。

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

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

          注意最终答案最大可以在 101110^11 的级别,需要开 long long

          代码瓶颈在排序,时间复杂度 O(mlogm)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
            @ 2024-6-1 18:33:12

            在这里,我使用了 Kruskal 算法解决这道题(想看Prim算法的移步别的题解)。

            思路:把边从边权大小从小到大排序,从 00 号开始遍历整个图,创建最小生成树,累加权值。使用一个优化后的并查集,如果所有边都在一个集中,则结束。输出权值总和。如果枚举完所有的点后仍达不到 n1n-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
              @ 2023-11-16 15:53:45

              最小生成树个人喜欢 KruskalKruskal 算法

              前置知识:贪心,并查集

              原理

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

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

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

              1. 如果 uuvv 两点之间没有路径,我们就将这条边加入到最小生成树中;
              2. 如果 uuvv 两点之间已经在最小生成树中有路径,或者形成了一个环,那么我们就把这条边"扔掉"。

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

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

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

              注意!!! 开long long!!!,0wi1060 \le w_i \le 10^6!!!

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

              它与 KruskalKruskal 的区别就在于一个是加点(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
                @ 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
                  @ 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
                    @ 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
                      @ 2022-8-18 17:05:49

                      KruskalKruskal 解决问题,ansans 注意开 longlonglong long ,不然会爆

                      下面是 ACAC 代码:

                      #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
                        @ 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
                          @ 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
                            @ 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
                              @ 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;
                              }
                              
                              • 1

                              Information

                              ID
                              91
                              Time
                              1000ms
                              Memory
                              256MiB
                              Difficulty
                              3
                              Tags
                              # Submissions
                              780
                              Accepted
                              255
                              Uploaded By