hdu 5441 并查集

By | 10月31日
Advertisement

Travel

Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 2331 Accepted Submission(s): 804

Problem Description

Jack likes to travel around the world, but he doesn’t like to wait. Now, he is traveling in the Undirected Kingdom. There are n
cities and m
bidirectional roads connecting the cities. Jack hates waiting too long on the bus, but he can rest at every city. Jack can only stand staying on the bus for a limited time and will go berserk after that. Assuming you know the time it takes to go from one city to another and that the time Jack can stand staying on a bus is x
minutes, how many pairs of city (a,b)
are there that Jack can travel from city a
to b
without going berserk?

Input

The first line contains one integer T,T≤5
, which represents the number of test case.
For each test case, the first line consists of three integers n,m
and q
where n≤20000,m≤100000,q≤5000
. The Undirected Kingdom has n
cities and m
bidirectional roads, and there are q
queries.
Each of the following m
lines consists of three integers a,b
and d
where a,b∈{1,...,n}
and d≤100000
. It takes Jack d
minutes to travel from city a
to city b
and vice versa.
Then q
lines follow. Each of them is a query consisting of an integer x
where x
is the time limit before Jack goes berserk.

Output

You should print q
lines for each test case. Each of them contains one integer as the number of pair of cities (a,b)
which Jack may travel from a
to b
within the time limit x
.
Note that (a,b)
and (b,a)
are counted as different pairs and a
and b
must be different cities.

Sample Input

1 5 5 3 2 3 6334 1 5 15724 3 5 5705 4 3 12382 1 3 21726 6000 10000 13000

Sample Output

2 6 12

Source

2015 ACM/ICPC Asia Regional Changchun Online

其实这道题 队里之前讲过的 一直没有写...gg

一直TLE 然后学习了离线并查集 先排序 一边扫 一边存 还有计算几对的姿势也不好 he+=mp[ss]*mp[ee]

然后 然后 按着这个敲了还是超时 gg 太菜比了 并查集 以为了解的很深了

如下正解

int Find(int mubiao)
{
if(parent[mubiao]!=mubiao)
parent[mubiao]=Find(parent[mubiao]);//原来的姿势一直有bug
return parent[mubiao];
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int t;
int n,m,q;
struct  path
{
    int s;
    int e;
    int dis;
     bool operator <(const path &x)const{
      return dis<x.dis;
     }
}P[100005];
struct limi
{
    int id;
    int limit;
    bool operator <(const limi &x)const{
      return limit<x.limit;
     }
}L[100005];
__int64 re[5005];
int parent[20005];
int mp[20005];
int Find(int mubiao)
{
    if(parent[mubiao]!=mubiao)
        parent[mubiao]=Find(parent[mubiao]);
    return parent[mubiao];
}
void init()
{
    for(int j=1;j<=n;j++)
    {
        parent[j]=j;
        mp[j]=1;
    }
    memset(re,0,sizeof(re));
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&q);
        for(int i=0;i<m;i++)
            scanf("%d%d%d",&P[i].s,&P[i].e,&P[i].dis);
        sort(P,P+m);
        for(int i=0;i<q;i++)
        {
            L[i].id=i;
            scanf("%d",&L[i].limit);
        }
        sort(L,L+q);
        init();
        int gg=0;
        __int64 he=0;
        for(int i=0;i<q;i++)
        {
            while(gg<m&&L[i].limit>=P[gg].dis)
            {
                int ss=Find(P[gg].s);
                int ee=Find(P[gg].e);
                if(ss!=ee)
                {
                    he+=mp[ss]*mp[ee];
                    parent[ee]=ss;
                    mp[ss]+=mp[ee];
                }
                gg++;
            }
            re[L[i].id]=he;
        }
        for(int i=0;i<q;i++)
            printf("%I64d\n",2*re[i]);
}
return 0;
}

Similar Posts:

  • hdu 1213 并查集用Kruskal算法

    http://acm.hdu.edu.cn/showproblem.php?pid=1213 题意就是说,有n个人参加的party,要准备多少张桌子,使得任意桌子上坐的人都是有联系的. 所谓有联系的就是说:比如A 和 B,如果他们两认识,或者存在一些人 C D E...使得A .B能够认识. 求最少要准备的桌子的数量. 解法:直接用并查集算法解决. 分析:把昨天的代码拿来稍微改了下,果断ac.水题飘过. View Code // I'm lanjiangzhou //C #include <st

  • hdu 1116 并查集

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1116 题目大意:给你一连串单词,看能否进行单词接龙,是这些单词形成一条链 思路:将每一个单词的首尾字母当做结点,首尾字母间连线,判断最后形成的有向图能否形成欧拉通路,用并查集 欧拉通路:除首尾结点外,其余结点入度等于出度,起点出度减入度等于1,终点入度减出度等于1 欧拉回路:所有结点的入度都等于出度 #include<stdio.h> #include<string.h> #defin

  • HDU 3371 并查集

    http://acm.hdu.edu.cn/showproblem.php?pid=3371 题意:给你一些分开的城市群,还给你一些城市相连的权值.让你求将所有城市相连所需的最小权值,不肯能输出-1. 解法:并查集. #include <iostream> #include <algorithm> using namespace std; int n,m,k,father[501],ans; struct node { int u,v,c; }st[300000]; void in

  • hdu 5438 并查集

    题目:hdu 5438 题意: 有一些池塘用管道连接着,但是主人没钱了,要清除一些与其他池塘相连数目少于2的池塘,包括一些独立的池塘.每个池塘都有一个价值,最后在删完一些池塘后求出有奇数个连通块的池塘的价值和. 分析: 记得是一道网络赛的题目.而且还记得我做的时候,用了deque,总是超时.又做了一下,好简单的题目.就是模拟一下删池塘的操作就好.先用并查集记录一下每个池塘所处的连通块,然后开始把不符合要求的池塘删去,最后把同一个连通块中并且度数大于1的池塘找出来,如果是奇数个,求一下和就好了.

  • HDU 2473 并查集的删除

    http://acm.split.hdu.edu.cn/showproblem.php?pid=2473 Junk-Mail Filter Time Limit: 15000/8000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8885    Accepted Submission(s): 2830 Problem Description Recognizing junk

  • HDU 1863 并查集+Kruskal

    点击打开链接 题意:不解释了 思路:也不解释了,并查集判段连通性,Kruskal求最小生成树,大水题(/ □ \) #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long lo

  • HDU 4514并查集判环+最长路

    点击打开链接 题意:中文题...... 思路:先判断能否成环,之前以为是有向图,就用了spfa判断,果断过不了自己出的样例,发现是无向图,并查集把,两个点有公共的父节点,那就是成环了,之后便是求最长路了,之前用spfa将权值取反后求最短路,然后结果取正就完事了,只是加个源点0而已,跑一边竟然能超时,难道是姿势不对吗.....,然后用了更暴力的bfs,因为是一个无环的图,所以从一个点出发后,它能走到的点之后便不用再走了,而这个点在bfs中更新距离时每个点只能入队一次.....这样就快多了,但是我们

  • hdu 1198 并查集应用

    其实可能是因为知道是用并查集做的原因啦,一下就看出题意了,明显是并查集思想,每次输入地图中的一块,检测这一块与它顶头的那块可不可以相通 如果可以合并集合;同理检测其与它左边的那一块;最后遍历一遍看有多少个根结点即要多少个水源 下面是代码,有点乱 #include<iostream> #include<vector> #define M 55 #define N 55 using namespace std; class elem{ public: bool up; bool dow

  • HDU 1198 并查集(感觉自己写的有点复杂)

    Farm Irrigation Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7928    Accepted Submission(s): 3427 Problem Description Benny has a spacious farm land to irrigate. The farm land is a rectangle

  • HDU 1116(并查集,欧拉路径)

    题意:给你一些英文单词,判断所有单词能不能连成一串,类似成语接龙的意思.但是如果有多个重复的单词时,也必须满足这样的条件才能算YES.否则都是不可能的情况. 解题思路: 欧拉路的基本题.只要知道就可以做出来了. 关于欧拉回路和欧拉路径 定义: 欧拉回路:每条边恰好只走一次,并能回到出发点的路径 欧拉路径:经过每一条边一次,但是不要求回到起始点 ①首先看欧拉回路存在性的判定: 一.无向图 每个顶点的度数都是偶数,则存在欧拉回路. 二.有向图(所有边都是单向的) 每个节顶点的入度都等于出度,则存在欧

Tags: