当前位置：首页 > news >正文

FZU-2087 统计树边(最小生成树)

news 来源：原创 2024/5/10 20:24:16

Problem 2087 统计树边

Accept: 223 Submit: 693
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

在图论中，树：任意两个顶点间有且只有一条路径的图。

生成树：包含了图中所有顶点的一种树。

最小生成树：对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，权最小的生成树称为G的最小生成树(Minimum Spanning Tree)。最小生成树可简记为MST。

但是，对于一个图而言，最小生成树并不是唯一的。

现在,给你一个连通的有权无向图，图中不包含有自环和重边，你的任务就是寻找出有多少条边，它至少在一个最小生成树里。图保证连通。

Input

输入数据第一行包含一个整数T，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数n,m(1<n<100000,n-1<m<100000)，接下来m行，每行三个整数a,b,v(1<=a,b<=n,1<v<500)，表示第i条路线连接景点A和景点B，距离是V。两个数字之间用空格隔开。

Output

对于每组测试数据，输出一行，包含一个整数，表示满足条件的边的个数。

Sample Input

1 4 5 1 2 101 1 3 100 2 3 2 2 4 2 3 4 1

Sample Output

Source

福州大学第九届程序设计竞赛

我们需要的是动态判断一条边权值相同的边能否可能是另一种生成树方法的边。我们直接在kruskal算法过程中加上动态判断的成分就可以了，那么要如何判断呢？遍历每一条边的时候，如果有相同权值的边，像kruskal一样的判断条件，判断这条边能否加入生成树中即可。

到现在还是有点迷糊，不过背代码大法好！

 1 #include "bits/stdc++.h"
 2 #define mem(a,b) memset(a,b,sizeof(a))
 3 using namespace std;
 4 typedef long long LL;
 5 const int MAX=100005;
 6 int n,m,T,ans;
 7 int fa[MAX];
 8 struct Edge{
 9     int u,v,w;
10     bool operator <(const Edge &cc) const {
11         return w<cc.w;
12     }
13 }edge[MAX];
14 void init(){
15     int i,j;
16     scanf("%d%d",&n,&m);
17     for (i=1;i<=m;i++){
18         scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
19     }
20     sort(edge+1,edge+m+1);
21     for (i=1;i<=n;i++)
22      fa[i]=i;
23     ans=0;
24 }
25 int getfather(int x){
26     if (fa[x]==x) return x;
27     else return fa[x]=getfather(fa[x]);
28 }
29 int main(){
30     freopen ("tree.in","r",stdin);
31     freopen ("tree.out","w",stdout);
32     int i,j,cas(0);
33     scanf("%d",&T);
34     while (T--){
35         init();
36         for (i=1;i<=m;i=j){
37             for (j=i;edge[j].w==edge[i].w;j++){
38                 if (getfather(edge[j].v)!=getfather(edge[j].u))
39                     ans++;
40             }
41             for (j=i;edge[j].w==edge[i].w;j++){
42                 int tx=getfather(edge[j].u);
43                 int ty=getfather(edge[j].v);
44                 if (tx!=ty)
45                  fa[tx]=ty;
46             }
47         }
48         printf("%d\n",ans);
49     }
50     return 0;
51 }