【tyvj1460】旅行

2014年3月20日2,22411

描述 Description

A国有n座城市,每座城市都十分美,这使得A国的民众们非常喜欢旅行。然而,A国的交通十分落后,这里只有m条双向的道路,并且这些道路都十分崎岖,有的甚至还是山路,只能靠步行。通过每条道路的长度、泥泞程度等因素,我们给每条道路评估一个“崎岖度”,表示通过这条道路的不舒适程度。
从X城市经过若干条道路到达Y城市,我们称这次旅行的“代价”为所经过道路“崎岖度”的最大值。当然,如果从X城市到Y城市有多条路线,民众们会自觉选择“代价”最小的路线进行旅行。但是,A国的民众也是有脾气的,如果旅行的“代价”超过了他们的“忍耐度”,他们就不选择这个旅行了,甚至宁愿在家里宅着。
现在A国的国王想进行若干次询问:给定民众的“忍耐度”,问还有多少对城市(X,Y)会存在旅行?请你对国王的每次询问分别给出回答。

输入格式 InputFormat

第1行三个正整数n、m、Q,分别表示城市数量、道路数量和询问次数。
第2行到第m+1行每行三个正整数x、y、w,表示x号城市和y号城市之间有一条“崎岖度”为w的双向道路。
第m+2行至第m+Q+1行,每行一个正整数k,表示询问中给定的“忍耐度”为k。

输出格式 OutputFormat

共Q行,对于每次询问做出回答。

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

【样例说明】
第一个询问:(1,2)、(1,5)、(2,5)、(3,4)。其中(2,5)的具体走法为:2-1-5
第二个询问:(1,2)、(1,3)、(1,4)、(1,5)、(2,3)、(2,4)、(2,5)、(3,4)、(3,5)、(4,5)。其中(4,5)的具体走法为:4-3-2-1-5
【数据规模】
对于20%的数据满足n<=20,m<=40,Q<=40;
对于40%的数据满足n<=1000,m<=2000,Q<=1000;
对于60%的数据满足n<=3000,m<=6000,Q<=200000;
对于100%的数据满足n<=100000,m<=200000,Q<=200000。其他数不超过10^9。
【细节提示】
1 给出的n个城市不一定全部互相连通,且两个城市之间可能存在多条道路,也可能存在某条边是从某城市出发回到他自己。
2 对于询问的结果可能很大,请注意使用适当的类型存储。

题解
先从小到大排序   然后利用并查集维护连通性更新答案   得到由边权划分出的答案表  二分查找输出即可。。

 

  • Ric_BRS2014年3月21日 下午8:43 回复

    我是看到图片才戳进来的……(呐文章其实还是不错的……)但是……图我找不到了怎么……

    #1  
    • hzwer2014年3月21日 下午9:27 回复
      admin

      什么图。。

      #11
      • Ric_BRS2014年3月23日 下午9:03 回复

        就是那些在目录里有的……相关文章里也有的……萌妹子的照片……= =

        #12
        • hzwer2014年3月23日 下午9:09 回复
          admin

          警察叔叔就是这个人

          #13
          • Ric_BRS2014年3月24日 下午6:12

            = =图呢……图呢……图呢………………………………………………

            #14
          • hzwer2014年3月24日 下午9:36
            admin

            乖出门左转oxgood

            #14
          • Ric_BRS2014年3月25日 下午6:23

            ~

            #14
    • 黑暗世界2014年3月24日 上午10:28 回复

      蒟蒻我也是看见这些图片然后就戳进来了,后面被这些萌萌的歌声吸引,就每天都来膜拜这位博主巨神啦~~

      #11
      • hzwer2014年3月24日 下午12:15 回复
        admin

        每天访问量没上过50。。。

        #12
        • hxw2016年11月6日 下午7:36 回复

          不会的吧我们机房几乎每天都看

          #13
  • 海之工作室2014年3月24日 下午6:14 回复

    强迫症看着这页的边栏好难受= =

    #2