hdu portal(经典)

这是一道好题,让我又学了一个新的知识,离线算法+并查集

题意:先给出图,求存在多少路径使得花费T小于L,T的定义是u,v亮点的所有路径的最大边的最小值

(Unfortunately, making a pair of portals will cost min{T} energies. T in a path between point V and point U is the length of the longest edge in the path)

分析:首先将需要询问的Q进行排序,从小到大,因为L的值大的必定包含了L值小的路径。然后将两点各自的集合相乘num[u]*num[v],可以细想一下,假设与u已经合并的点有2个,与v合并的点有3个,那么u,v两集合所能组成的点就是2*3,因为两集合当前存储的边必定都小于T,而且必定都小于T,然后再讲u,v两集合合并,形成新的集合num[u]。对于边的查找,只需要找到小于等于T就可以停止查找,我们可以看一下,当u,v边长为L‘加入,且L'>L,若u,v在一个集合,则新通路为0,因为这两点的路径个数在以前加过了,若u,v在两个集合,则它们之间只有一条通路,可想而知,这条通路的权值为L‘,则无论组成的哪天连通两点的路径其最大边都为L’。

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAXN= 50010;

struct Edge
{
    int a,b,l;
} edge[MAXN];

struct Node
{
    int t,pos;
} pl[MAXN/5];

int father[MAXN/5],num[MAXN/5];
long long temp[MAXN/5];

bool cmp1(Edge a,Edge b)
{
    return a.l<b.l;
}

bool cmp2(Node a,Node b)
{
    return a.t<b.t;
}

void Make_set(int n)
{
    for (int i=1; i<=n; i++)
    {
        father[i]=i;
        num[i]=1;
    }
}

int Find(int x)
{
    int r=x;
    while(r!=father[r])//这里写错了。。
    {
        r=father[r];
    }
    if(r!=x) father[x]=r;
    return father[x];
}

int Union(int s1,int s2)
{
    int x=Find(s1);
    int y=Find(s2);
    if(x==y) return 0;
    long long  t=num[x]*num[y];
    num[x]+=num[y];//祖先代表该集合的总点数
    num[y]=0;//当成为一个集合只需要有个祖先就够了,其他的点为了避免重复均=0
    father[y]=x;
    return t;
}

int main()
{
    int n,m,q,i;
    while(scanf("%d%d%d",&n,&m,&q)!=EOF)
    {
        Make_set(n);
        for(i=0; i<m; i++)
        {
            scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].l);
        }
        sort(edge,edge+m,cmp1);
        for(int k=0; k<q; k++)
        {
            scanf("%d",&pl[k].t);
            pl[k].pos=k;
        }
        sort(pl,pl+q,cmp2);
        long long  ans=0;
        int pos=0;
        for(i=0; i<q; i++)
        {
            while(pos<m && edge[pos].l<=pl[i].t)
            {
                ans+=Union(edge[pos].a,edge[pos].b);
                pos++;
            }
            temp[pl[i].pos]=ans;
        }
        for(i=0; i<q; i++)
        {
            printf("%lld\n",temp[i]);
        }
    }
    return 0;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

圆排列问题-回溯法

问题描述:     给定n个大小不等的圆 c1 c2 c3 c4 要将n个圆排进一个矩形框中,且要求底边相切。找出有最小长度的圆排列。     例如:当n=3,...

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

P1387 最大正方形

题目描述 在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形,输出边长。 输入输出格式 输入格式: 输入文件第一行为两个整数n,m(1<=n...

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

cf547D. Mike and Fish(欧拉回路)

1234
来自专栏闻道于事

Java异常处理中的恢复模型

2774
来自专栏蓝天

sed 学习笔记(转)

声明:这些代码只是为了学习和理解sed命令而为之,并不代表问题的唯一解或最佳解,希望各位拍砖

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

LOJ#6281. 数列分块入门 5

内存限制:256 MiB时间限制:500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计讨论 1 测试数据 题...

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

LOJ#6279. 数列分块入门 3

内存限制:256 MiB时间限制:1500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计讨论 1 测试数据 ...

3599
来自专栏企鹅号快讯

Windows路径转换为Msys2表示的Linux路径

实现功能: H:\MySpace\PluginConfig 转换为: /h/MySpace/PluginConfig ? 实现代码 #!/usr/bin/gaw...

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

洛谷P3808 【模板】AC自动机(简单版)

subtask1[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6,n=1;

1082
来自专栏开发与安全

从零开始学C++之虚继承和虚函数对C++对象内存模型造成的影响(类/对象的大小)

首先重新回顾一下关于类/对象大小的计算原则: 类大小计算遵循结构体对齐原则 第一个数据成员放在offset为0的位置 其它成员对齐至min(sizeof(me...

2230

扫码关注云+社区

领取腾讯云代金券