contesthunter 6201 走廊泼水节【克鲁斯卡尔+并查集】

时间:2022-09-05 14:24:48

很有意思的题,所以还是截lyddalao的课件

contesthunter 6201 走廊泼水节【克鲁斯卡尔+并查集】

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=6005;
int T,n,f[N],s[N];
long long ans;
struct qwe
{
int u,v,w;
}a[N];
bool cmp(const qwe &a,const qwe &b)
{
return a.w<b.w;
}
int read()
{
int r=0,f=1;
char p=getchar();
while(p>'9'||p<'0')
{
if(p=='-')
f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
r=r*10+p-48;
p=getchar();
}
return r*f;
}
int zhao(int x)
{
return x==f[x]?x:zhao(f[x]);
}
int main()
{
T=read();
while(T--)
{
n=read();ans=0;
for(int i=1;i<n;i++)
a[i].u=read(),a[i].v=read(),a[i].w=read();
sort(a+1,a+n,cmp);
for(int i=1;i<=n;i++)
f[i]=i,s[i]=1;
for(int i=1;i<n;i++)
{
int fu=zhao(a[i].u),fv=zhao(a[i].v);
ans+=1ll*s[fu]*s[fv]*(a[i].w+1)-a[i].w-1;//cerr<<ans<<endl;
f[fu]=fv;
s[fv]+=s[fu];
}
printf("%lld\n",ans);
}
return 0;
}

contesthunter 6201 走廊泼水节【克鲁斯卡尔+并查集】的更多相关文章

  1. 最小生成树 - 克鲁斯卡尔 - 并查集 - 边稀疏 - O&lpar;E &ast; logE&rpar;

    #define _CRT_SECURE_NO_WARNINGS #include<cstdio> #include<cstring> #include<algorithm ...

  2. ACM程序设计选修课——Problem E&colon;&lpar;ds&colon;图&rpar;公路村村通(优先队列或sort&plus;克鲁斯卡尔&plus;并查集优化)

    畅通工程 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submi ...

  3. CH 6201 走廊泼水节题解

    题目链接:CH6201 当时在海亮考试的第一题: 心得:其实一个算法是要真正理解这个思路和过程,而并不是单单知道它是用来写什么题的: 思路:n个节点有n-1条边,把这n-1条边按照权值从小到大排序,有 ...

  4. CH6201 走廊泼水节【最小生成树】

    6201 走廊泼水节 0x60「图论」例题 描述 [简化版题意]给定一棵N个节点的树,要求增加若干条边,把这棵树扩充为完全图,并满足图的唯一最小生成树仍然是这棵树.求增加的边的权值总和最小是多少. 我 ...

  5. 图的生成树(森林)(克鲁斯卡尔Kruskal算法和普里姆Prim算法)、以及并查集的使用

    图的连通性问题:无向图的连通分量和生成树,所有顶点均由边连接在一起,但不存在回路的图. 设图 G=(V, E) 是个连通图,当从图任一顶点出发遍历图G 时,将边集 E(G) 分成两个集合 T(G) 和 ...

  6. hdu 1233&lpar;还是畅通project&rpar;(prime算法,克鲁斯卡尔算法)(并查集,最小生成树)

    还是畅通project Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Tota ...

  7. hdu5441 并查集&plus;克鲁斯卡尔算法

    这题计算 一张图上 能走的 点对有多少个  对于每个限制边权 , 对每条边排序,对每个查询排序 然后边做克鲁斯卡尔算法 的时候变计算就好了 #include <iostream> #inc ...

  8. 贪心算法&lpar;Greedy Algorithm&rpar;之最小生成树 克鲁斯卡尔算法&lpar;Kruskal&amp&semi;&num;39&semi;s algorithm&rpar;

    克鲁斯卡尔算法(Kruskal's algorithm)是两个经典的最小生成树算法的较为简单理解的一个.这里面充分体现了贪心算法的精髓.大致的流程能够用一个图来表示.这里的图的选择借用了Wikiped ...

  9. 贪心算法&lpar;Greedy Algorithm&rpar;最小生成树 克鲁斯卡尔算法&lpar;Kruskal&amp&semi;&num;39&semi;s algorithm&rpar;

    克鲁斯卡尔算法(Kruskal's algorithm)它既是古典最低的一个简单的了解生成树算法. 这充分反映了这一点贪心算法的精髓.该方法可以通常的图被表示.图选择这里借用Wikipedia在.非常 ...

随机推荐

  1. 使用forever管理nodejs应用

    1. forever介绍 forever是一个简单的命令式nodejs的守护进程,能够启动,停止,重启App应用.forever完全基于命令行操作,在forever进程之下,创建node的子进程,通过 ...

  2. 阿里大鱼&period;net core 发送短信

    阿里大鱼还未提供 .net core 版SDK,但提供了相关API,下面是.net core版实现,只是简单发送短信功能: using System; using System.Collections ...

  3. NPOI Excel类

    using System;using System.Collections.Generic;using System.Linq;using System.Text;using NPOI.HSSF.Us ...

  4. 2016030204 - git和github结合

    1.下载和安装git客户端 参考:http://www.cnblogs.com/zhtzyh2012/p/5232291.html 2.github上创建项目 参考:http://www.cnblog ...

  5. android术语笔记

    参考:http://blog.csdn.net/luoshengyang/article/details/6618363 http://blog.csdn.net/singwhatiwanna/art ...

  6. React是什么,为什么要使用它?

    React是Facrbook内部的一个JavaScript类库,已于1年开源,可用于创建Web用户交互界面.它引入了一种新的方式来处理浏览器DOM.那些需要手动更新DOM.费力地记录每一个状态的日子一 ...

  7. Android ConstraintLayout 布局警告

    使用 ConstraintLayout 布局出现警告: 此视图不受垂直约束.在运行时,除非添加垂直约束,否则它将跳转到左侧 解决办法: 从Android Studio v3及更高版本开始,从下拉列表中 ...

  8. Windos上生成密钥,以及添加到GIT

    1.下载git //进入官网下载git; https://git-scm.com/download/win 2.配置本地信息 git config --g user.name "wbiokr ...

  9. 【Python】exe2shellcode,shellcode2exe

    用python写这类程序真简洁,要是用C++又不知道得多写多少行代码了. exe2shellcode #! /usr/bin/env python # -*- coding: utf-8 -*- im ...

  10. 记一次web服务模块开发过程

    一.前言 之前在分析WCS系统的过程中,也赶上要开发其中的一个模块,用于和AGV系统对接完成一些取货.配盘等任务:在这里将这次模块开发的全过程记录一下,以便自己以后开发时能够更加快速的明白流程. 二. ...