[关闭]
@DATASOURCE 2015-08-07T09:13:33.000000Z 字数 20496 阅读 2068

生成树

图论

最小生成树

概述

在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且为无循环图，使得 的 w(T) 最小，则此 T 为 G 的最小生成树。
最小生成树其实是最小权重生成树的简称。 许多应用问题都是一个求无向连通图的最小生成树问题。例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

性质

• 最小生成树的边数必然是顶点数减一，|E| = |V| - 1。
• 最小生成树不可以有环。
• 最小生成树不必是唯一的。

Prim 算法

描述

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

主要操作

从单一顶点开始，Prim算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。
  • 输入：一个加权连通图，其中顶点集合为V，边集合为E；
  • 初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {}；

  • 重复下列操作，直到Vnew = V：

    • 在集合E中选取权值最小的边（u, v），其中u为集合Vnew中的元素，而v则不是（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
    • 将v加入集合Vnew中，将（u, v）加入集合Enew中；

  • 输出：使用集合Vnew和Enew来描述所得到的最小生成树。过程如图所示：

复杂度分析

通过邻接矩阵图表示的简易实现中，找到所有最小权边共需O（V2）的运行时间。使用简单的二叉堆与邻接表来表示的话，普里姆算法的运行时间则可缩减为O(E log V)，其中E为连通图的边数，V为顶点数。如果使用较为复杂的斐波那契堆，则可将运行时间进一步缩短为O(E + V log V)，这在连通图足够密集时（当E满足Ω（V log V）条件时），可较显著地提高运行速度。

代码示例

  1. //邻接矩阵：
  2. #define N 10000
  3. #define M 0x3f3f3f3f
  4. int n;                                          // n 是点的数目；
  5. int map[N][N], low[N], div[N];                      // map[N][N] 存储点和权值，low[N]中存储未收录到树的
  6. int prim(){                                     // 点到树的最小距离，div记录已经收录到树中的点。
  7.     int i, j, min, minp, sum = 0;
  8.     for(i = 0; i < n; i++)                              // 初始化div[N] 数组的值 0 为未收录该点，1 为收录。
  9.         div[i] = 0;
  10.     div[0] = 1;
  11.     minp = 0;
  12.     for(i = 1; i < n; i++)                              // 第一次初始化low[N] 数组，存储个点到minp的距离
  13.         low[i] = map[minp][i];
  14.     for(i = 1; i < n; i++){
  15.         min = M;
  16.         for(j = 0; j < n; j++)
  17.             if(div[j] == 0 && min > low[j]){            // 找出距离minp 最小的点，用minp记录，并记距离
  18.                 min = low[j];
  19.                 minp = j;
  20.             }
  21.         div[minp] = 1;                              // 上一个过程中找到的点被收录到树中，并加上权值
  22.         sum += min;
  23.         for(j = 0; j < n; j++){                         // 更新low[N] 数组，使其始终保持未收录到树中的点
  24.             if(div[j] == 0 && low[j] > map[minp][j])     // 到树的最小距离。
  25.                 low[j] = map[minp][j];
  26.         }
  27.     }
  28.     return sum;
  29. }
  1. //邻接表：
  2. #include <queue>
  3. #include <cstdio>
  4. #include <iostream>
  5. #define N 100
  6. #define M (1 << 30)
  7. using namespace std;
  9. struct Edge{
  10.     int v, w, n;
  11. };
  12. struct Node{
  13.     int v, w;
  15.     friend bool operator < (const Node &a, const Node &b){
  16.         return a.w > b.w;
  17.     }
  18. };
  20. int head[N], dis[N], n, m, e;
  21. bool vis[N];
  22. Edge edge[N * N / 2];
  23. priority_queue < Node > que;
  25. void init(){
  26.     e = 0;
  27.     while(!que.empty()) que.pop();
  28.     fill(head, head + N, -1);
  29.     fill(dis, dis + N, M);
  30.     fill(vis, vis + N, false);
  31. }
  33. void addedge(int u, int v, int w){
  34.     edge[e].v = v;
  35.     edge[e].w = w;
  36.     edge[e].n = head[u];
  37.     head[u] = e++;
  38. }
  40. int prime(){
  41.     int ans = 0;
  42.     Node t;
  43.     t.v = 1;
  44.     t.w = 0;
  45.     que.push(t);
  46.     int nume = 0;
  47.     while(!que.empty() && nume <= m){
  48.         t = que.top();
  49.         que.pop();
  50.         if(vis[t.v]) continue;
  51.         ans += t.w;
  52.         vis[t.v] = true;
  53.         nume++;
  54.         for(int i = head[t.v]; i != -1; i = edge[i].n)
  55.             if(!vis[edge[i].v]){
  56.                 Node tt;
  57.                 tt.v = edge[i].v;
  58.                 tt.w = edge[i].w;
  59.                 que.push(tt);
  60.             }
  61.     }
  62. If(nume == n) return ans;
  63. return -1;
  64. }
  66. int main(){
  67.     while(scanf("%d", &n) != EOF && n){
  68.         scanf("%d", &m);
  69.         init();
  70.         int a, b, w;
  71.         for(int i = 0; i < m; i++){
  72.             scanf("%d%d%d", &a, &b, &w);
  73.             addedge(a, b, w);
  74.             addedge(b, a, w);
  75.         }
  76.         printf("%d\n", prime());
  77.     }
  78.     return 0;
  79. }

Kruskal 算法

描述

假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。

主要操作

1).记Graph中有v个顶点，e个边

2).新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边

3).将原图Graph中所有e个边按权值从小到大排序

4).循环：从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中
if 这条边连接的两个节点于图Graphnew中不在同一个连通分量中添加这条边到图Graphnew中；

过程如图所示：

复杂度分析

从Kruskal算法中可以看到，执行该算法时间主要花费在堆排序和单层循环上，而循环是线性级的，则可以认为时间复杂性主要花费在堆排序上，由堆排序算法可知，Kruskal算法的时间复杂度为O(eloge)，其中e为图的边数。

代码示例：

  1. #define M 10000                         // M 为最多的点的数目
  3. struct maps{                                // 定义新类型，maps x，y代表两个点，w为他们的权值；
  4.     int x, y, w;
  5. };
  7. maps map[M * M];
  8. int par[M], n, ne;                          // n 为实际点的数目，ne为两个不同的点构成的边的数目
  10. bool cmp(const maps& a, const maps& b){     // sort 函数调用将边按权值由小到大排序
  11.     return a.w < b.w;
  12. }
  14. void init(){                                // 以下为并查集内容
  15.     int i;
  16.     for(i = 1; i <= n; i++)
  17.         par[i] = i;
  18. }
  20. int find(int x){
  21.     if(par[x] != x)
  22.         par[x] = find(par[x]);
  23.     return par[x];
  24. }
  26. bool unit(int x, int y){
  27.     int fx = find(x);
  28.     int fy = find(y);
  29.     if(fx != fy){
  30.         par[fy] = fx;
  31.         return true;
  32.     }
  33.     return false;
  34. }
  36. int kruscal(){
  37.     int i, sum = 0;
  38.     b = 0;                                      // b为加入树中的边的数目；
  39.     sort(map, map + ne, cmp);                       // 排序；
  40.     for(i = 1; i <= ne; i++){
  41.         if(unit(map[i].x, map[i].y)){                   // 当两点至少有一个未收录到树中时，向树中加入该边
  42.             sum += map[i].w;                        // 这样做是为了防止树中出现环路；
  43.             b++;
  44.             if(b == n - 1)                          // 当边数比点数少1时，所有的点被收录到树中；
  45.                 break;
  46.         }
  47.     }
  48.     return sum;
  49. }

POJ 例题分析

POJ 1751

  • 题目大意：一个有n个城市的国家，已知有些城市有道路联通，问增加哪些道路使得所有的城市都可以彼此联通且代价最小，已经代价是两个城市坐标的笛卡尔距离；

    • 输入：n 表示有九个点，接下来n行将输入这就个点的坐标，之后会有一个整数q代表已经有q条边连接，接下来q行将输入这q条边所连接的点（例如： 1 2 代表上面所输入的n个坐标的第一个和第二个点已经连接。
    • 输出：输出还需要连接的点，用空格隔开（已经连号的点不能输出）。

  • 解题思路：Prim 算法，因为这道题目已经有一些边连起来了，故在初始化map数组时，连起来的边要置为零，由于该题要求输出被连接的两个点，在算法内部可以用一个数组来记录当前正在验证的边的端点，此外，已经连接的点不能输出，故当权值为零时则不输出。

  1. //代码示例：
  2. #include<iostream>
  3. #include<iomanip>
  4. #define M 800
  5. #define MAXINT 1<<28
  6. using namespace std;
  8. struct a{                                           // 定义结构体来存放点的坐标；
  9.     int x , y;
  10. };
  12. int map[M][M], low[M];
  13. int vis[M], p[M];                                   // 数组 P 用来存放 low 数组中权值所对应的点
  14. int n, q;
  15. a s[M];
  17. void prim(){
  18.     int i, j, minp, f = 0;                              // f用来标记权值是否为零；
  19.     int min;
  20.     for(i = 1; i <= n; i++)
  21.         vis[i] = 0;
  22.     vis[1] = 1;
  23.     minp = 1;
  24. for(i = 2; i <= n; i++){                            
  25.         p[i] = minp;                              // p 数组用来存放 low 数组中的权值所对应的点
  26.         low[i] = map[minp][i];
  27.     }
  28.     for(i = 1; i < n; i++){
  29.         min = MAXINT;
  30.         for(j = 1; j <= n; j++)
  31.             if(vis[j] == 0 && min > low[j] && minp != j){       // minp != j 即跳过边的两端为同一个点的情况
  32.                 minp = j;
  33.                 min = low[j];
  34.                 if(map[p[j]][minp] == 0)                    // 若权值为零，则标记下来；
  35.                     f = 1;
  36.                 else
  37.                     f = 0;
  38.             }
  39.         vis[minp] = 1;
  40.         if(f == 0)                                      // 权值为零时不输出；
  41.             cout<< p[minp] <<" "<< minp <<endl;
  42.         mina = minp;
  43.         for(j = 1; j <= n; j++)
  44.             if(vis[j] == 0 && map[minp][j] < low[j]){
  45.                 p[j] = minp;
  46.                 low[j] = map[minp][j];
  47.             }
  48.     }
  49. }
  52. int main(){
  53.     int i, j, a, b;
  54.     int l;
  55.     cin >> n;
  56.     for(i = 1; i <= n; i++)
  57.         cin >> s[i].x >> s[i].y;
  58.     for(i = 1; i <= n; i++){
  59.         for(j = 1; j <= n; j++){
  60.             l = (s[i].x - s[j].x) * (s[i].x - s[j].x) + (s[i].y - s[j].y) * (s[i].y - s[j].y);
  61.             map[i][j] = map[j][i] = l;                          // 注意无向图应该两个方向的值相同；
  62.         }
  63.     }
  64.     cin >> q;
  65.     for(i = 1; i <= q; i++){
  66.         cin >> a >> b;
  67.         map[a][b] = map[b][a] = 0;                          // 已经连起来的边权值为零；
  68.     }
  69.     prim();
  70.     return 0;
  71. }
Kruskal 算法,注意在本题上的使用技巧，题目要求不输出已经连接的边的端点，故可以在初始化的时候将连接好的端点加入集合中，这样在kruskal算法执行过程中就不会涉及到那些边。

  1. //代码示例：
  2. #include<cstdio>
  3. #include<stdio.h>
  4. #include<algorithm>
  5. #include<iostream>
  6. #define N 755
  7. using namespace std;
  9. struct maps{
  10.     int x, y, w;
  11. };
  13. struct s{                                           // 存储点的坐标
  14.     int x, y;
  15. };
  17. bool cmp(const maps& a, const maps& b){
  18.     return a.w < b.w;
  19. }
  21. maps map[N * N];
  22. s s[N];
  23. int par[N];
  24. int n, ne, b;
  26. void init(){
  27.     int i;
  28.     for(i = 1; i <= n; i++)
  29.         par[i] = i;
  30. }
  32. int find(int x){
  33.     if(par[x] != x)
  34.         par[x] = find(par[x]);
  35.     return par[x];
  36. }
  38. bool unit(int x, int y){
  39.     int fx = find(x);
  40.     int fy = find(y);
  41.     if(fx != fy){
  42.         par[fy] = fx;
  43.         return true;
  44.     }
  45.     return false;
  46. }
  48. void kruscal(){
  49.     int i, sum = 0;
  50.     b = 0;
  51.     sort(map, map + ne, cmp);
  52.     for(i = 1; i <= ne; i++){
  53.         if(unit(map[i].x, map[i].y)){
  54.             cout << map[i].x << " " << map[i].y << endl;
  55.             b++;
  56.             if(b == n - 1)
  57.                 break;
  58.         }
  59.     }
  60. }
  62. int main(){
  63.     int i, j, l, q, a;
  64.     ne = 0;
  65.     ios_base::sync_with_stdio(false);
  66.     cin >> n;
  67.     init();
  68.     for(i = 1; i <= n; i++)
  69.        cin >> s[i].x >> s[i].y;
  70.     for(i = 1; i <= n; i++)
  71.         for(j = 1; j <= n; j++)
  72.             if(i != j){                                 // 避免重（chong）点
  73.                 l = (s[i].x - s[j].x) * (s[i].x - s[j].x) + (s[i].y - s[j].y) * (s[i].y - s[j].y);
  74.                 map[ne].x = i;
  75.                 map[ne].y = j;
  76.                 map[ne].w = l;
  77.                 ne++;
  78.             }
  79.    cin >> q;
  80.     for(i = 0; i < q; i++){
  81.        cin >> a >> b;
  82.         par[find(b)] = par[find(a)];                        // 已经连起来的边的端点收录到集合中；
  83.         b++;                                            // 记录边的条数；
  84.     }
  85.     kruscal();
  86.     return 0;
  87. }
POJ 2966


  • 题目大意：一个图中有几个连通分支（并不是每个点与其他点都有连接，只有一部分边） 。你可以连通任意两个点。求在满足使这个图成为连通图的前提下，使你所连的两点间的边的sum(权值)最小。

    • 输入：第一行为case个数，每个case里的第一行为两个数N和E分别表示点的个数和边的条数，接下来的E行是两个点和他们的权值。
      *输出：每个case输出一行，即连接这些点的最小权值。
    • 解题思路: Prim 算法，最小生成树最基本的题目，只要把map数组初始化为很大的值，就可以在程序运行中避开那些不能连接的边。
  1. //代码示例：
  2. #include <iostream>
  3. #define M 505
  4. #define MAXINT 1000 
  5. using namespace std;
  7. int map[M][M], low[M], vis[M];
  8. int t, e, n;
  10. void prim(){
  11.     int i, j, min, minp, key = 0;
  12.     min = MAXINT;
  13.     for(i = 0; i < n; i++)                  
  14.         vis[i] = 0;
  15.     vis[0] = 1;
  16.     minp = 0;
  17.     for(i = 0; i < n; i++)
  18.         low[i] = map[minp][i];
  19.     for(i = 0; i < n - 1; i++){
  20.         min = MAXINT;
  21.         for(j = 0; j < n; j++)
  22.             if(min > low[j] && vis[j] == 0){
  23.                 min = low[j];
  24.                 minp = j;
  25.             }
  26.         key += min;
  27.         vis[minp] = 1;
  28.         for(j = 0; j < n; j++)
  29.             if(vis[j] == 0 && map[minp][j] < low[j])
  30.                 low[j] = map[minp][j]; 
  31.     }
  32.     cout<< key <<endl;
  33. }
  37. int main(){
  38.     ios_base::sync_with_stdio(false);
  39.     int i, j, k, c;
  40.     cin >> t;
  41.     while(t--){
  42.         for(i = 0; i < M; i++)
  43.             for(j = 0; j < M; j++)
  44.                 map[i][j] = MAXINT;             // 初始化为很大的值
  45.         cin >> n >> e;
  46.         for(k = 0; k < e; k++){
  47.             cin >> i >> j;
  48.             cin >> c;
  49.             map[j][i] = map[i][j] = c;
  50.         } 
  51.         prim();
  52.     }
  53.     return 0;
  54. }
Kruskal 算法：没技巧，直接套模版。

  1. //代码示例：
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #define N 505
  6. using namespace std;
  8. struct maps{
  9.     int x, y, w;
  10. };
  12. maps map[N * N];
  13. int par[N], n, e;
  15. bool cmp(const maps& a, const maps& b){
  16.     return a.w < b.w;
  17. }
  19. void init(){
  20.     int i;
  21.     for(i = 0; i <= n; i++){
  22.        par[i] = i;
  23.     }
  24. }
  26. int find(int x){
  27.     if(par[x] != x)
  28.         par[x] = find(par[x]);
  29.     return par[x];
  30. }
  32. bool unit(int x, int y){
  33.     int fx = find(x);
  34.     int fy = find(y);
  35.     if(fx != fy){
  36.         par[fy] = fx;
  37.         return true;
  38.     }
  39.     return false;
  40. }
  42. void kruscal(){
  43.     int i, b = 0, sum = 0;
  44.     init();
  45.     sort(map, map + e, cmp);
  46.     for(i = 0; i < e; i++)
  47.         if(unit(map[i].x, map[i].y)){
  48.             sum += map[i].w;
  49.             b++;
  50.             if(b == n - 1){
  51.                 printf("%d\n", sum);
  52.                 break;
  53.             }
  54.         }
  55. }
  57. int main(){
  58.     int i, j, t, x, y, cost;
  59.     scanf("%d", &t);
  60.     while(t--){
  61.         scanf("%d %d", &n, &e);
  62.         for(i = 0; i < e; i++){
  63.             scanf("%d %d %d", &x, &y, &cost);
  64.             map[i].x = x;
  65.             map[i].y = y;
  66.             map[i].w = cost;
  67.         }
  68.         kruscal();
  69.     }
  70.     return 0;
  71. }

次小生成树（k小生成树）

概述

给出一个带边权的无向图G，设其最小生成树为T，求出图G的与T不完全相同的边权和最小的生成树（即G的次小生成树）。一个无向图的两棵生成树不完全相同，当且仅当这两棵树中至少有一条边不同。注意，图G可能不连通，可能有平行边，但一定没有自环（其实对于自环也很好处理：直接舍弃。因为生成树中不可能出现自环）。定义生成树T的一个可行变换(-E1, +E2)：将T中的边E1删除后，再加入边E2（满足边E2原来不在T中但在G中），若得到的仍然是图G的一棵生成树，则该变换为可行变换，该可行变换的代价为(E2权值 - E1权值)。这样，很容易证明，G的次小生成树就是由G的最小生成树经过一个代价最小的可行变换得到。进一步可以发现，这个代价最小的可行变换中加入的边E2的两端点如果为V1和V2，那么E1一定是原来最小生成树中从V1到V2的路径上的权值最大的边。

prim算法

描述

设立数组F，F[x][y]表示T中从x到y路径上的最大边的权值。F数组可以在用Prim算法求最小生成树的过程中得出。每次将边(i, j)加入后（j是新加入树的边，i=c[j]），枚举树中原有的每个点k（包括i，但不包括j），则F[k][j]=max{F[k][i], (i, j)边权值}，又由于F数组是对称的，可以得到F[j][k]=F[k][j]。然后千万记住将图G中的边(i, j)删除（就是将邻接矩阵中(i, j)边权值改为∞）！因为T中的边是不能被加入的。等T被求出后，所有的F值也求出了，然后，枚举点i、j，若邻接矩阵中边(i, j)权值不是无穷大（这说明i、j间存在不在T中的边），则求出{(i, j)边权值 - F[i][j]}的值，即为加入边(i, j)的代价，求最小的总代价即可。
  • 另外注意三种特殊情况：
    1. 图G不连通，此时最小生成树和次小生成树均不存在。判定方法：在扩展T的过程中找不到新的可以加入的边；
    2. 图G本身就是一棵树，此时最小生成树存在（就是G本身）但次小生成树不存在。判定方法：在成功求出T后，发现邻接矩阵中的值全部是无穷大；
    3. 图G存在平行边。这种情况最麻烦，因为这时代价最小的可行变换(-E1, +E2)中，E1和E2可能是平行边！
      因此，只有建立两个邻接矩阵，分别存储每两点间权值最小的边和权值次小的边的权值，然后，每当一条新边(i, j)加入时，不是将邻接矩阵中边(i, j)权值改为无穷大，而是改为连接点i、j的权值次小的边的权值。

代码示例

  1. #include <ctime>
  2. #include <cstdio>
  3. #include <iostream>
  4. #include <algorithm>
  5. #define M (1 << 30)
  6. #define N 2010
  7. using namespace std;
  9. int mp[N][N], mp1[N][N], ma[N][N], pre[N], dis[N], n, m, ans, res;
  10. bool vis[N];        //mp1 存储次小边，ma存储每一条路径的最大值 pre 前驱
  12. void init(){
  13.     fill(mp[0], mp[N], M);
  14.     fill(mp1[0], mp1[N], M);
  15.     fill(ma[0], ma[N], 0);
  16.     fill(dis, dis + N, M);
  17.     fill(vis, vis + N, false);
  18.     scanf("%d%d", &n, &m);
  19.     int u, v, w;
  20.     for(int i = 0; i < m; i++){
  21.         scanf("%d%d%d", &u, &v, &w);
  22.         if(w < mp[u][v]){
  23.             mp1[u][v] = mp[u][v];
  24.             mp[u][v] = w;
  25.             mp1[v][u] = mp1[u][v];
  26.             mp[v][u] = mp[u][v];
  27.         }else if(w < mp1[u][v]){
  28.             mp1[u][v] = w;
  29.             mp1[v][u] = mp1[u][v];
  30.         }
  31.     }
  32. }
  34. int prim(int s){
  35.     ans = 0, res = M;
  36.     int mi, mip;
  37.     for(int i = 1; i <= n; i++){
  38.         dis[i] = mp[s][i];
  39.         pre[i] = s;
  40.     }
  41.     vis[s] = true;
  42.     for(int i = 1; i < n; i++){
  43.         mi = M, mip = 0;
  44.         for(int j = 1; j <= n; j++){
  45.             if(!vis[j] && dis[j] < mi){
  46.                 mi = dis[j];
  47.                 s = pre[j];
  48.                 mip = j;
  49.             }
  50.         }
  51.         if(mi == M) return 0;               // 返回 0 时，说明不存在最小生成树
  52.         ans += mi;
  53.         vis[mip] = true;
  54.         mp[s][mip] = M;
  55.         mp[mip][s] = M;
  56.         if(mp1[s][mip] < M && mp1[s][mip] - mi < res)
  57.             res = mp1[s][mip] - mi;
  58.         for(int j = 1; j <= n; j++)
  59.             if(!vis[j] && dis[j] > mp[mip][j]){
  60.                 dis[j] = mp[mip][j];
  61.                 pre[j] = mip;
  62.             }
  63.         for(int j = 1; j <= n; j++)
  64.             if(vis[j] && j != s && j != mip){
  65.                 ma[j][mip] = max(ma[j][s], mi);
  66.                 ma[mip][j] = ma[j][mip];    
  67.             }
  68.     }
  69.     for(int i = 1; i <= n; i++)
  70.         for(int j = 1; j <= n; j++)
  71.             if(i != j && mp[i][j] != M)
  72.                 res = min(res, mp[i][j] - ma[i][j]);
  73.     if(res == M) return 1;                 // 返回 1 时， 说明不存在次小生成树
  74.     res += ans;                         // 之前的 res 都代表 E2-E1
  75.     return 2;                           // 返回 2 时， 说明存在次小生成树
  76. }
  78. int main(){
  79.     int t;
  80.     //clock_t start = clock();
  81.     scanf("%d", &t);
  82.     for(int i = 1; i <= t; i++){
  83.         init();
  84.         int ch = prim(1);
  85.         printf("Case %d: ", i);
  86.         if(ch == 0) printf("-1\n");
  87.         else if(ch == 1) printf("%d %d\n", ans, -1);
  88.         else printf("%d %d\n", ans, res);
  89.     }
  90.     //clock_t stop = clock();
  91.     //printf("Time = %.2lfMS\n", (double)(stop - start) / CLOCKS_PER_SEC * 1000);
  92.     return 0;
  93. }
  1. //拓展只求两个点间的最大边
  2. int prime(int s){
  3.     int mi, mip, ans;
  4.     mip = s;
  5.     vis[mip] = 1;
  6.     for(int i = 0; i < n; i++)
  7.         low[i] = mp[mip][i], pre[i] = s;
  8.     for(int i = 1; i < n; i++){
  9.         mi = MAX;
  10.         for(int j = 0; j < n; j++)
  11.             if(!vis[j] && mi > low[j])
  12.                 mi = low[j], mip = j, s = pre[j];
  13.         ans += mi;
  14.         vis[mip] = 1;
  15.         for(int j = 0; j < n; j++){
  16.             if(vis[j] && j != mip){
  17.                 ma[j][mip] = ma[j][s] > mi ? ma[j][s] : mi;
  18.                 ma[mip][j] = ma[j][mip];
  19.             } if(!vis[j] && low[j] > mp[mip][j])
  20.                 low[j] = mp[mip][j], pre[j] = mip;
  21.         }
  22.     }
  23.     return ans;
  24. }

Kruskal算法

描述

Kruskal算法也可以用来求次小生成树。在准备加入一条新边(a, b)（该边加入后不会出现环）时，选择原来a所在连通块（设为S1）与b所在连通块（设为S2）中，点的个数少的那个（如果随便选一个，最坏情况下可能每次都碰到点数多的那个，时间复杂度可能增至O(NM)），找到该连通块中的每个点i，并遍历所有与i相关联的边，若发现某条边的另一端点j在未选择的那个连通块中（也就是该边(i, j)跨越了S1和S2）时，就说明最终在T中"删除边(a, b)并加入该边"一定是一个可行变换，且由于加边是按照权值递增顺序的，(a, b)也一定是T中从i到j路径上权值最大的边，故这个可行变换可能成为代价最小的可行变换，计算其代价为[(i, j)边权值 - (a, b)边权值]，取最小代价即可。注意，在遍历时需要排除一条边，就是(a, b)本身（具体实现时由于用DL边表，可以将边(a, b)的编号代入）。另外还有一个难搞的地方：如何快速找出某连通块内的所有点？方法：由于使用并查集，连通块是用树的方式存储的，可以直接建一棵树（准确来说是一个森林），用“最左子结点+相邻结点”表示，则找出树根后遍历这棵树就行了，另外注意在合并连通块时也要同时合并树。
  • 对于三种特殊情况：
    【1】 图G不连通。判定方法：遍历完所有的边后，实际加入T的边数小于(N-1)；
    【2】 图G本身就是一棵树。判定方法：找不到这样的边(i, j)；
    【3】 图G存在平行边。这个对于Kruskal来说完全可以无视，因为Kruskal中两条边只要编号不同就视为不同的边。
    其实Kruskal算法求次小生成树还有一个优化：每次找到边(i, j)后，一处理完这条边就把它从图中删掉，因为当S1和S2合并后，(i, j)就永远不可能再是可行变换中的E2了。

代码示例

  1. #include <iostream>
  2. #include <stdlib.h>
  3. using namespace std;
  4. #define re(i, n) for (int i=0; i<n; i++)
  5. #define re3(i, l, r) for (int i=l; i<=r; i++)
  6. const int MAXN = 7000, MAXM = 130000, INF = ~0U >> 2;
  8. struct edge {
  9.     int a, b, len, pre, next;
  10. } ed[MAXM + MAXM];
  12. struct edge2 {
  13.     int a, b, len, No;
  14. } ed2[MAXM];
  16. int n, m = 0, m2, u[MAXN], ch[MAXN], nx[MAXN], q[MAXN], res1 = 0, res2 = INF;
  18. void init_d(){
  19.     for(int i - 0; i < n; i++){
  20.         ed[i].a = ed[i].pre = ed[i].next = i;
  21.     if (n % 2) m = n + 1; 
  22.     else m = n;
  23. }
  25. void add_edge(int a, int b, int l) {
  26.     ed[m].a = a; ed[m].b = b; ed[m].len = l; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
  27.     ed[m].a = b; ed[m].b = a; ed[m].len = l; ed[m].pre = ed[b].pre; ed[m].next = b; ed[b].pre = m; ed[ed[m].pre].next = m++;
  28. }
  30. void del_edge(int No){
  31.     ed[ed[No].pre].next = ed[No].next; 
  32.     ed[ed[No].next].pre = ed[No].pre;
  33.     ed[ed[No ^ 1].pre].next = ed[No ^ 1].next; 
  34.     ed[ed[No ^ 1].next].pre = ed[No ^ 1].pre;
  35. }
  37. void init() {
  38.     scanf("%d%d", &n, &m2);
  39.     if (!m2) {
  40.         if (n > 1) res1 = -INF;
  41.         res2 = -INF; 
  42.         return;
  43.     }
  44.     init_d();
  45.     int a, b, len;
  46.     for(int i = 0; i < m2; i++){
  47.         scanf("%d%d%d", &a, &b, &len);
  48.         ed2[i].No = m; add_edge(--a, --b, len);
  49.         ed2[i].a = a; ed2[i].b = b; ed2[i].len = len;
  50.     }
  51. }
  53. int cmp(const void *s1, const void *s2) {
  54.     return ((edge2 *)s1)->len - ((edge2 *)s2)->len;
  55. }
  57. void prepare() {
  58.     for(int i = 0; i < n; i++){
  59.         u[i] = ch[i] = nx[i] = -1;
  60.     qsort(ed2, m2, 16, cmp);
  61. }
  63. int find(int x){
  64.     int r = x, r0 = x, tmp;
  65.     while (u[r] >= 0) r = u[r];
  66.     while (u[r0] >= 0) {
  67.         tmp = u[r0]; 
  68.         u[r0] = r; 
  69.         r0 = tmp;
  70.     }
  71.     return r;
  72. }
  74. void uni(int r1, int r2, int No, int l0) {
  75.     q[0] = r1;
  76.     int j, k, l1, front, rear;
  77.     for (front = 0, rear = 0; front <= rear; front++) {
  78.         j = ch[q[front]];
  79.         while (j != -1) {
  80.             q[++rear] = j;
  81.             j = nx[j];
  82.         }
  83.     }
  84.     for(int i = 0; i <= rear; i++){
  85.         j = q[i];
  86.         for (int p=ed[j].next; p != j; p=ed[p].next) {
  87.             k = ed[p].b;
  88.             if (p != No && find(k) == r2) {
  89.                 l1 = ed[p].len - l0;
  90.                 if (l1 < res2) res2 = l1;
  91.                 del_edge(p);
  92.             }
  93.         }
  94.     }
  95.     u[r2] += u[r1]; u[r1] = r2; nx[r1] = ch[r2]; ch[r2] = r1;
  96. }
  98. void solve() {
  99.     int r1, r2, l0, num = 0;
  100.     for(int i = 0; i < m2; i++){
  101.         r1 = find(ed2[i].a); 
  102.         r2 = find(ed2[i].b);
  103.         if (r1 != r2) {
  104.             l0 = ed2[i].len; 
  105.             res1 += l0; 
  106.             num++;
  107.             if (u[r1] >= u[r2]) uni(r1, r2, ed2[i].No, l0); 
  108.             else uni(r2, r1, ed2[i].No ^ 1, l0);
  109.         }
  110.     }
  111.     if (num < n - 1) {
  112.         res1 = res2 = -INF; 
  113.         return;
  114.     }
  115.     if (res2 == INF) res2 = -INF; 
  116.     else res2 += res1;
  117. }
  119. void pri() {
  120.     printf("Cost: %d\nCost: %d\n", res1 == -INF ? -1 : res1, res2 == -INF ? -1 : res2);
  121. }
  123. int main() {
  124.     init();
  125.     if (!res1 && res2 == INF) {
  126.         prepare();
  127.         solve();
  128.     }
  129.     pri();
  130.     return 0;
  131. }
  1. //另解
  2. //#include <ctime>
  3. #include <cstdio>
  4. #include <iostream>
  5. #include <algorithm>
  6. #define N 100100
  7. #define M (1 << 29)
  8. #define Max(a, b) (a > b ? a : b)
  9. using namespace std;
  11. struct Edge{
  12.     int a, b, w;
  13.     friend bool operator < (const Edge &a, const Edge &b){
  14.         return a.w < b.w;
  15.     }
  16. };
  17. class LCA{
  18. public:
  19.     struct Edge{
  20.         int v, n, w;
  21.         void init(int a, int b, int c){
  22.             v = a, n = b, w = c;
  23.         }
  24.     };
  25.     Edge tedge[2 * N], qedge[2 * N], aedge[2 * N];
  26.     int thead[N], qhead[N], ahead[N];
  27.     int vis[N], par[N], ma[2 * N], ans[2 * N];
  28.     int te, qe, ae;
  30.     void init(){
  31.         te = qe = ae = 0;
  32.         fill(ma, ma + 2 * N, -M);
  33.         for(int i = 0; i < N; i++){
  34.             par[i] = i;
  35.             thead[i] = qhead[i] = ahead[i] = -1;
  36.             //ma[i] = -M;
  37.             vis[i] = false;
  38.         }
  39.     }
  41.     int find(int x){
  42.         int temp = par[x];
  43.         if(x != temp) par[x] = find(par[x]);
  44.         ma[x] = Max(ma[x], ma[temp]);
  45.         return par[x];
  46.     }
  48.     void addEdge(int *head, Edge *edge, int u, int v, int w, int &e){
  49.         edge[e].v = v, edge[e].w = w, edge[e].n = head[u], head[u] = e++;
  50.         if(head == ahead) return;
  51.         edge[e].v = u, edge[e].w = w, edge[e].n = head[v], head[v] = e++;
  52.     }
  54.     void dfs(int a){
  55.         vis[a] = 1;
  56.         for(int i = qhead[a]; i + 1; i = qedge[i].n){
  57.             int b = qedge[i].v;
  58.             if(vis[b]){
  59.                 int temp = find(b);
  60.                 addEdge(ahead, aedge, temp, a, i, ae);
  61.             }
  62.         }
  63.         for(int i = thead[a]; i + 1; i = tedge[i].n){
  64.             int b = tedge[i].v;
  65.             if(vis[b] == 0){
  66.                 dfs(b);
  67.                 par[b] = a;
  68.                 ma[b] = tedge[i].w;
  69.             }
  70.         }
  71.         for(int i = ahead[a]; i + 1; i = aedge[i].n){
  72.             int x = aedge[i].v;
  73.             int t = aedge[i].w;
  74.             int y = qedge[t].v;
  75.             find(x);
  76.             find(y);
  77.             ans[qedge[t].w] = Max(ma[x], ma[y]);
  78.         }
  79.     }
  80. }lca;
  82. int par[N], n, m;
  83. Edge edge[2 * N];
  84. bool vis[N];
  86. void init(){
  87.     for(int i = 0; i < N; i++)
  88.         par[i] = i, vis[i] = false;
  89. }
  91. int find(int x){
  92.     if(par[x] != x) par[x] = find(par[x]);
  93.     return par[x];
  94. }
  96. bool Union(int x, int y){
  97.     int fx = find(x);
  98.     int fy = find(y);
  99.     if(fx == fy) return false;
  100.     par[fx] = fy;
  101.     return true;
  102. }
  104. int Kruscal(){
  105.     int ne = 0, ans = 0;
  106.     sort(edge, edge + m);
  107.     for(int i = 0; i < m; i++)
  108.         if(Union(edge[i].a, edge[i].b)){
  109.             ans += edge[i].w;
  110.             ne++;
  111.             vis[i] = true;
  112.             lca.addEdge(lca.thead, lca.tedge, edge[i].a, edge[i].b, edge[i].w, lca.te);
  113.             if(ne == n - 1) break;
  114.         }
  115.     if(ne == n - 1) return ans;
  116.     return -1;
  117. }
  119. int Ckruscal(){
  120.     int res = M, me = 0, ne = 0;
  121.     for(int i = 0; i < m; i++)
  122.         if(!vis[i]) lca.addEdge(lca.qhead, lca.qedge, edge[i].a, edge[i].b, me++, lca.qe);
  123.     lca.dfs(1);
  124.     for(int i = 0; i < m; i++)
  125.         if(!vis[i]){
  126.             if(edge[i].w - lca.ans[ne] < res) res = edge[i].w - lca.ans[ne];
  127.             ne++;
  128.         }
  129.     if(res < M) return res;
  130.     return -1;
  131. }
  133. int main(){
  134.     //clock_t start = clock();
  135.     int t;
  136.     scanf("%d", &t);
  137.     for(int j = 1; j <= t; j++){
  138.         //printf("Case %d: ", j);
  139.         scanf("%d%d", &n, &m);
  140.         int a, b, w;
  141.         init();
  142.         lca.init();
  143.         for(int i = 0; i < m; i++){
  144.             scanf("%d%d%d", &a, &b, &w);
  145.             edge[i].a = a, edge[i].b = b, edge[i].w = w;
  146.         }
  147.         int ans = Kruscal();
  148.         if(ans == -1){
  149.             printf("%d\n", ans);
  150.             continue;
  151.         }else{
  152.             int res = Ckruscal();
  153.             printf("%d %d\n", ans, res == -1 ? -1 : ans + res);
  154.         }
  155.     }
  156.     //clock_t stop = clock();
  157.     //printf("Time = %.2lfMS\n", (double)(stop - start) / CLOCKS_PER_SEC * 1000);
  158.     return 0;
  159. }

复杂度分析

效率分析：可以证明，如果每次都选取点少的连通块，Kruskal算法求次小生成树的时间复杂度为O(M*(logN+logM))，空间复杂度为O(M)。

总结：显然Prim适用于稠密图，而Kruskal适用于稀疏图。

生成树个数

Matrix-Tree定理(Kirchhoff矩阵-树定理)。Matrix-Tree定理是解决生成树计数问题最有力的武器之一。它首先于1847年被Kirchhoff证明。在介绍定理之前，我们首先明确几个概念：
1、G的度数矩阵D[G]是一个n*n的矩阵，并且满足：当i≠j时,dij=0；当i=j时，dij等于vi的度数。

2、G的邻接矩阵A[G]也是一个n*n的矩阵， 并且满足：如果vi、vj之间有边直接相连，则aij=1，否则为0。

我们定义G的Kirchhoff矩阵(也称为拉普拉斯算子)C[G]为C[G]=D[G]-A[G]，则Matrix-Tree定理可以描述为：G的所有不同的生成树的个数等于其Kirchhoff矩阵C[G]任何一个n-1阶主子式的行列式的绝对值。所谓n-1阶主子式，就是对于r(1≤r≤n)，将C[G]的第r行、第r列同时去掉后得到的新矩阵，用Cr[G]表示。

最小生成树的个数

算法思想：

抛开“最小”的限制不看,如果只要求求出所有生成树的个数,是可以利用Matrix-Tree定理解决的;  Matrix-Tree定理此定理利用图的Kirchhoff矩阵,可以在O(N3)时间内求出生成树的个数;
kruskal算法：
将图G={V,E}中的所有边按照长度由小到大进行排序,等长的边可以按照任意顺序; 
初始化图G’为{V,?},从前向后扫描排序后的边,如果扫描到的边e在G’中连接了两个相异的连通块,则将它插入G’中; 
最后得到的图G’就是图G的最小生成树; 

由于kruskal按照任意顺序对等长的边进行排序,则应该将所有长度为L0的边的处理当作一个阶段来整体看待; 

令kruskal处理完这一个阶段后得到的图为G0,如果按照不同的顺序对等长的边进行排序,得到的G0也是不同; 

虽然G0可以随排序方式的不同而不同,但它们的连通性都是一样的,都和F0的连通性相同(F0表示插入所有长度为L0的边后形成的图); 

在kruskal算法中的任意时刻,并不需要关注G’的具体形态,而只要关注各个点的连通性如何(一般是用并查集表示); 

所以只要在扫描进行完第一阶段后点的连通性和F0相同,且是通过最小代价到达这一状态的,接下去都能找到最小生成树; 

经过上面的分析,可以看出第一个阶段和后面的工作是完全独立的; 

第一阶段需要完成的任务是使G0的连通性和F0一样,且只能使用最小的代价; 
计算出这一阶段的方案数,再乘上完成后续事情的方案数,就是最终答案; 
由于在第一个阶段中,选出的边数是一定的,所有边的长又都为L0; 
所以无论第一个阶段如何进行代价都是一样的,那么只需要计算方案数就行了; 
此时Matrix-Tree定理就可以派上用场了,只需对F0中的每一个连通块求生成树个数再相乘即可;
代码示例
  1. //#include <ctime>
  2. #include <queue>
  3. #include <cstdio>
  4. #include <vector>
  5. #include <iostream>
  6. #include <algorithm>
  7. #define N 1100
  8. using namespace std;
  10. typedef long long LL;
  11. const int mod = 10000;
  13. struct Edge{
  14.     int a, b, w;
  16.     bool operator < (const Edge &a) const{
  17.         return w < a.w;
  18.     }
  19. };
  21. int n, m;
  22. LL par[N], fa[N], vis[N];
  23. LL mp[N][N], mp1[N][N];
  24. Edge edge[N];
  26. vector <int> vec[N];
  28. void Swap(LL &a, LL &b){
  29.     a = a ^ b;
  30.     b = a ^ b;
  31.     a = a ^ b;
  32. }
  34. void init(){
  35.     scanf("%d%d", &n, &m);
  36.     fill(mp[0], mp[N], 0);
  37.     for(int i = 0; i <= n; i++){
  38.        vec[i].clear();
  39.        par[i] = i;
  40.        vis[i] = 0;
  41.     }
  42.     for(int i = 0; i < m; i++)
  43.         scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].w);
  44. }
  46. int find(int x, LL father[]){
  47.     if(x != father[x]) father[x] = find(father[x], father);
  48.     return father[x];
  50.     /*
  51.     if(x == father[x]) return x;
  52.     return find(father[x], father);
  53.     */
  54. }
  56. LL Mtree(LL a[][N], int n){
  57.     for(int i = 0; i < n; i++)
  58.         for(int j = 0; j < n; j++)
  59.             a[i][j] %= mod;
  60.     int ans = 1;
  61.     for(int i = 1; i < n; i++){
  62.         for(int j = i + 1; j < n; j++)
  63.             while(a[j][i]){
  64.                 int temp = a[i][i] / a[j][i];
  65.                 for(int k = i; k < n; k++)
  66.                     a[i][k] = (a[i][k] - a[j][k] * temp) % mod;
  67.                 for(int k = i; k < n; k++)
  68.                     Swap(a[i][k], a[j][k]);
  69.                 ans = -ans;
  70.             }
  71.         if(a[i][i] == 0) return 0;
  72.         ans = ans * a[i][i] % mod;
  73.     }
  74.     return (ans + mod) % mod;
  75. }
  77. void Solve(){
  78.     if(n == 1){
  79.         printf("1\n");
  80.         return;
  81.     }
  82.     sort(edge, edge + m);
  83.     LL flag = -1;
  84.     LL ans = 1;
  85.     for(int k = 0; k <= m; k++){
  86.         if(edge[k].w != flag || k == m){
  87.             for(int i = 1; i <= n; i++){
  88.                 if(vis[i]){
  89.                     LL u = find(i, fa);
  90.                     vec[u].push_back(i);
  91.                     vis[i] = 0;
  92.                 }
  93.             }
  94.             for(int i = 1; i <= n; i++){
  95.                 if(vec[i].size() > 1){
  96.                     fill(mp1[0], mp1[n + 1], 0);
  97.                     int len = vec[i].size();
  98.                     for(int a = 0; a < len; a++){
  99.                         int a1 = vec[i][a];
  100.                         for(int b = a + 1; b < len; b++){
  101.                             int b1 = vec[i][b];
  102.                             mp1[a][b] = (mp1[b][a] -= mp[a1][b1]);
  103.                             mp1[a][a] += mp[a1][b1];
  104.                             mp1[b][b] += mp[a1][b1];
  105.                         }
  106.                     }
  107.                     LL res = (LL)Mtree(mp1, len);
  108.                     ans = (ans * res) % mod;
  109.                     for(int a = 0; a < len; a++)
  110.                         par[vec[i][a]] = i;
  111.                 }
  112.             }
  113.             for(int i = 1; i <= n; i++){
  114.                 fa[i] = par[i] = find(i, par);
  115.                 vec[i].clear();
  116.             }
  117.             if(k == m) break;
  118.             flag = edge[k].w;
  119.         }
  120.         int a = edge[k].a;
  121.         int b = edge[k].b;
  122.         int a1 = find(a, par);
  123.         int b1 = find(b, par);
  124.         if(a1 == b1) continue;
  125.         vis[a1] = vis[b1] = 1;
  126.         fa[find(a1, fa)] = find(b1, fa);
  127.         mp[a1][b1]++;
  128.         mp[b1][a1]++;
  129.     }
  130.     int flag1 = 0;
  131.     for(int i = 2; i <= n && !flag1; i++)
  132.         if(fa[i] != fa[i - 1]) flag1 = 1;
  133.     if(m == 0) flag1 = 1;
  134.     printf("%lld\n", flag1 ? 0 : ans % mod);
  135. }
  137. int main(){
  138.     //clock_t start = clock();
  139.     int t;
  140.     scanf("%d", &t);
  141.     for(int i = 1; i <= t; i++){
  142.         init();
  143.         Solve();
  144.     }
  145.     //clock_t stop = clock();
  146.     //printf("Time = %.2lfMS\n", (double)(stop - start) / CLOCKS_PER_SEC * 1000);
  147.     return 0;
  148. }
  1. //另解：
  2. //#include <ctime>
  3. #include <queue>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <iostream>
  7. #include <algorithm>
  8. #define N 550
  9. #define Mod 10000
  10. using namespace std;
  12. struct Edge{
  13.     int a, b, w;
  15.     friend bool operator < (const Edge &a, const Edge &b){
  16.         return a.w < b.w;
  17.     }
  18. };
  20. int par[N], fa[N], cnt[N], ne[N];
  21. int n, m, len, from, to;
  22. Edge edge[N];
  24. void init(int *par, int n){
  25.     for(int i = 0; i <= n; i++)
  26.         par[i] = i;
  27. }
  29. int find(int *par, int x){
  30.     if(par[x] != x) par[x] = find(par, par[x]);
  31.     return par[x];
  32. }
  34. void dfs(int pos, int num, int &ans){
  35.     if(num == len){
  36.         init(fa, N);
  37.         for(int i = 0; i < from; i++){
  38.             int fx = find(fa, edge[i].a);
  39.             int fy = find(fa, edge[i].b);
  40.             if(fx != fy) fa[fy] = fx;
  41.         }
  42.         for(int i = 0; i < len; i++){
  43.             int di = ne[i];
  44.             int fx = find(fa, edge[di].a);
  45.             int fy = find(fa, edge[di].b);
  46.             if(fx != fy) fa[fy] = fx;
  47.             else return;
  48.         }
  49.         ans++;
  50.     }else{
  51.         for(int i = pos; i <= to; i++){
  52.             ne[num] = i;
  53.             dfs(i + 1, num + 1, ans);
  54.         }
  55.     }
  56. }
  58. void solve(){
  59.     int ans = 1;
  60.     from = to = 0;
  61.     init(par, n);
  62.     edge[m].w = -1;
  63.     cnt[0] = 0;
  64.     for(int i = 0; i < m; i++){
  65.         int fx = find(par, edge[i].a);
  66.         int fy = find(par, edge[i].b);
  67.         if(i) cnt[i] = cnt[i - 1];
  68.         if(fx != fy){
  69.             par[fy] = fx;
  70.             cnt[i]++;
  71.         }
  72.         if(edge[i].w != edge[i + 1].w){
  73.             if(!from) len = cnt[i];
  74.             else len = cnt[i] - cnt[from - 1];
  75.             if(len == 0) continue;
  76.             to = i;
  77.             int c = 0;
  78.             dfs(from, 0, c);
  79.             from = i + 1;
  80.             ans = ans * c % Mod;
  81.         }
  82.     }
  83.     if(cnt[m - 1] == n - 1) printf("%d\n", ans);
  84.     else printf("%d\n", 0);
  85. }
  87. int main(){
  88.     int t;
  89.     scanf("%d", &t);
  90.     while(t--){
  91.         scanf("%d%d", &n, &m);
  92.         for(int i = 0; i < m; i++)
  93.             scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].w);
  94.         sort(edge, edge + m);
  95.         solve();
  96.     }
  97.     return 0;
  98. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注