文档章节

【codevs 1450】小天昊的旅行2333333

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:57
字数 417
阅读 0
收藏 0

我滴妈这个题好神啊……
Q == Question
A == LOI_a

Q:我去这题怎么做
A:我看看……
A:数据范围?
Q:200000……
A:这题能做?
Q:QAQ
A:我回去看看
(两分钟后)
A:先跑个最小生成树,恩恩,然后在合并两棵树的时候,这条边一定是最大的,那么统计下答案,是左边的大小 * 右边的大小
Q:QAQ
A:显然这个数组是单调的,二分查找下就行
Q:Orz

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 200000 + 5;
struct edge
{
    int f,t,v;
    bool operator < (const edge &b)const
    {
        return v < b.v;
    }
}l[MAXN];
int n,m;
int fa[MAXN],size[MAXN];
void init()
{
    for(int i = 1;i <= n;i ++)
        fa[i] = i,size[i] = 1;
    return;
}
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool same(int x,int y)
{
    return find(x) == find(y);
}
void merge(int x,int y)
{
    x = find(x);
    y = find(y);
    if(size[x] > size[y])
        swap(x,y);
    fa[x] = y;
    size[y] += size[x];
    return;
}
int tot;
int val[MAXN];//对答案有贡献的边i的权值为val[i] 
long long ans[MAXN];//对答案有贡献的边i的答案为ans[i] 
void Kruskal()
{
    sort(l + 1,l + m + 1);
    init();
    tot = 0;
    for(int i = 1;i <= m;i ++)
    {
        if(same(l[i].f,l[i].t))
            continue;
        tot ++;
        int z_size = size[find(l[i].f)];
        int y_size = size[find(l[i].t)];
        val[tot] = l[i].v;
        ans[tot] = z_size * y_size + ans[tot - 1];
        merge(l[i].f,l[i].t);
    }
    tot++;
    val[tot] = 2147483647;
    ans[tot] = (long long)n * n;
    return;
}
long long answer(int v)
{
    int k = upper_bound(val + 1,val + tot + 1,v) - (val);
    return ans[k - 1];
}
int q;
int f,t,v;
int main()
{
    scanf("%d %d %d",&n,&m,&q);
    for(int i = 1;i <= m;i ++)
        scanf("%d %d %d",&l[i].f,&l[i].t,&l[i].v);
    Kruskal();
    while(q --)
    {
        scanf("%d",&v);
        printf("%lld\n",answer(v));
    }
    return 0;
}

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
寒假训练片头曲~

今天上午终于考完期末考的最后一门-线代。 (考完线代查了查C++面向对象程序设计的成绩,啧啧,要是那一次旷课没被抓住从而扣了三分的话,大概就考满分了2333333) 然后回到宿舍吃完饭开始睡...

Akatsuki__Itachi
2018/01/15
0
0
2333

2333333

slcigh
2016/02/29
1
1
2333

2333333

slcigh
2016/02/29
1
0
2333

2333333

slcigh
2016/02/29
2
0
2333

2333333

slcigh
2016/02/29
1
0

没有更多内容

加载失败,请刷新页面

加载更多

只需一步,在Spring Boot中统一Restful API返回值格式与统一处理异常

统一返回值 在前后端分离大行其道的今天,有一个统一的返回值格式不仅能使我们的接口看起来更漂亮,而且还可以使前端可以统一处理很多东西,避免很多问题的产生。 比较通用的返回值格式如下:...

晓月寒丶
今天
58
0
区块链应用到供应链上的好处和实际案例

区块链可以解决供应链中的很多问题,例如记录以及追踪产品。那么使用区块链应用到各产品供应链上到底有什么好处?猎头悬赏平台解优人才网小编给大家做个简单的分享: 使用区块链的最突出的优...

猎头悬赏平台
今天
27
0
全世界到底有多少软件开发人员?

埃文斯数据公司(Evans Data Corporation) 2019 最新的统计数据(原文)显示,2018 年全球共有 2300 万软件开发人员,预计到 2019 年底这个数字将达到 2640万,到 2023 年达到 2770万。 而来自...

红薯
今天
61
0
Go 语言基础—— 通道(channel)

通过通信来共享内存(Java是通过共享内存来通信的) 定义 func service() string {time.Sleep(time.Millisecond * 50)return "Done"}func AsyncService() chan string {retCh := mak......

刘一草
今天
57
0
Apache Flink 零基础入门(一):基础概念解析

Apache Flink 的定义、架构及原理 Apache Flink 是一个分布式大数据处理引擎,可对有限数据流和无限数据流进行有状态或无状态的计算,能够部署在各种集群环境,对各种规模大小的数据进行快速...

Vincent-Duan
今天
58
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部