图论板子最小生成树-白红宇

图论板子最小生成树

阅读量：4493 次

发布时间：2019-06-08

本文共 1564 字，大约阅读时间需要 5 分钟。

kruskal算法前向星+并查集需排序（加边，还有一种加点的prim算法，不惯用，就不更了

排序后每次找权值最小的两节点组成的边，加入树，通过并查集确定公共祖先，若某边加入会出现环，跳过，直至所有点都加入树，该树即为最小生成树

板子

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;const int INF=0x3f3f3f3f;typedef pair
              
                pr;typedef long long ll;#define fi first#define se second#define me(x) memset(x, -1, sizeof(x))#define mem(x) memset(x, 0, sizeof(x))#define MAXN 500000+5#define NIL -1struct node{ int u, v, w;}edge[MAXN];bool cmp(node a, node b){ if(a.w==b.w && a.u==b.u) return a.v
               
                 3 --> 4 --> 5 return r;}int mix() //合并 联通{ for(int i=0; i
                
                 >n>>m) { ans=0; for(i=1; i<=n; i++) p[i]=i; //初始化每个点的父节点为本身 for(i=0; i
                 
                  >edge[i].u>>edge[i].v>>edge[i].w; sort(edge, edge+m, cmp); mix(); cout<
                  
                   <

模板题

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 using namespace std;typedef long long ll;#define me(x) memset(x, -1, sizeof(x))#define mem(x) memset(x, 0, sizeof(x))const int MOD = 1e18;const int N = 2e6 + 5;int a[1005][1005], vis[1005][1005];struct node{ int u, v, d;}e[N];int p[N];int n, m, id, ans;void ini(){ id=0; mem(vis);}void add(int u, int v, int d){ e[id].u = u; e[id].v = v; e[id].d = d; id++;}bool cmp(node a, node b){ if(a.d==b.d && a.u==b.u) return a.v