FZU 2087 统计树边

Problem 2087 统计树边 Accept: 197 Submit: 571 Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

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

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

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

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

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

Input

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

第一行包含两个整数n,m(1

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <stdio.h>

using namespace std;
#define MAX 100000
struct Node
{
    int x;
    int y;
    int w;
}a[MAX+5];
int father[MAX+5];
int n,m;
int find(int x)
{
    if(x!=father[x])
        father[x]=find(father[x]);
    return father[x];
}
int cmp(Node a,Node b)
{
    return a.w<b.w;
}
int main()
{
    int t;
    scanf("%d",&t);
    int x,y,z;
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            a[i].x=x;
            a[i].y=y;
            a[i].w=z;
        }
        sort(a,a+m,cmp);
        for(int i=1;i<=n;i++)
            father[i]=i;
        int ans=0;
        int i=0;
        while(i<m)
        {
            int j=i;
            while(a[j].w==a[j+1].w)
            {
                int xx=find(a[j].x);
                int yy=find(a[j].y);
                if(xx!=yy)
                    ans++;
                j++;
            }
            int xx=find(a[j].x);
            int yy=find(a[j].y);
            if(xx!=yy)
                ans++;
            j=i;
            while(a[j].w==a[j+1].w)
            {
                int xx=find(a[j].x);
                int yy=find(a[j].y);
                if(xx!=yy)
                    father[xx]=yy;
                j++;
            }
            xx=find(a[j].x);
            yy=find(a[j].y);
            if(xx!=yy)
                father[xx]=yy;
            i=j+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏生信小驿站

Python数据处理从零开始----第四章(可视化)(7)(多图合并)目录正文

=========================================================

871
来自专栏数据结构与算法

洛谷P2678 跳石头

题目背景 一年一度的“跳石头”比赛又要开始了! 题目描述 这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终...

3435
来自专栏程序生活

Leetcode-Easy 70. Climbing Stairs

21. Merge Two Sorted Lists 描述: 有n阶楼梯,每步只能走1个或2个台阶,请问到达第n阶楼梯一共有多少走法? ? ...

3296
来自专栏转载gongluck的CSDN博客

H.264格式分析

一.H.264基本流结构 H.264 的基本流(elementary stream,ES)的结构分为两层,包括视频编码层(VCL)和网络适配层(NAL)。视频编...

7525
来自专栏CVPy

利用 Python 优雅地可视化数据

最近看《机器学习系统设计》的前两章,学到了一些用Matplotlib进行数据可视化的方法。在这里整理一下。

8880
来自专栏编程理解

数据结构(十二):最短路径(Dijkstra算法)

Dijkstra 算法使用贪心策略计算从起点到指定顶点的最短路径,通过不断选择距离起点最近的顶点,来逐渐扩大最短路径权值,直到覆盖图中所有顶点。

2982
来自专栏云霄雨霁

加权有向图----单点最短路径问题(Dijkstra算法)

2540
来自专栏数据结构与算法

1038 一元三次方程求解

1038 一元三次方程求解 2001年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver ...

2888
来自专栏bboysoul

1475: C语言实验题――一元二次方程 II

描述:求一元二次方程ax2+bx+c=0的解。a,b,c为任意实数。 输入:输入数据有一行,包括a b c的值 输出:按以下格式输出方程的根x1和x2。x1...

1253
来自专栏温安适的blog

最小生产树Prim和Kruskal

47512

扫码关注云+社区

领取腾讯云代金券