TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3855
  • 题目
  • P3855merlin
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 2s
    问题描述

    古月族是一个神奇的种族,有一天古月腾和古月豪在一起看《梅林传奇(merlin)》。

    剧中,以卡梅洛特(camelot)为代表的是古时英格兰的城池坐落在现我大英帝国的某处土地上,每个城池被乌瑟王(亚瑟王之父)编号,方便货物来往。

    假设有n座城池,编号为1-n,一些城池之间有单向道连接(逆向行驶会被视为私自入境),共k条。如果有一些城池能够互相到达交通无碍,他们会结为盟友,于是大英帝国上出现了许多帮派,他们要么互相挑起战争,要么选择井水不犯河水,形势极其尴尬,甚至,他们把连到其他帮派外的单向边拆毁了。

    现在,乌瑟王死后,亚瑟王想要统一大英,他决定让魔法师梅林在一些城池之间修一些双向边,这样能使所有城池互相联系,交流,促进和平发展。梅林为了帮助亚瑟王,他把可能会修的道路都进行了魔法加特,使走上这条路的人心平气和,向往和平。虽然梅林魔法强大,但他也需要休息,他只能在指定的城池之间建立m条双向边,并且每条双向边上的有一个魔力需求值wi。

    梅林已经累趴下了,谁叫亚瑟王这么折磨他(可怜的梅子),他想知道;

    1. 怎样连边,才能让所有城池能够互相到达,并且他耗费的魔力最少,求出这个最小值。
    2. 是否有不同种建边的方法。
    输入格式

    多组测试数据。

         第一行一个正整数T,对于每一组测试数据:

         第一行,三个个整数n,k,m。

    接下来k行,每行两个整数,x,y,表示从x城池到y城池有一条单向道路。

    接下来m行,每行三个整数,x,y,z,表示可以在城池x和城池y之间,建立一条双向道路,消耗魔法值为z。

    输出格式

    对于每一组测试数据:

    第一行,一个整数表示消耗最少魔力。

    第二行,若有不同的建边方法,输出“YES”,否则输出“NO”(均不含引号)。

    样例输入 1

    1
    5 5 5
    1 2
    2 3
    3 1
    3 4
    4 5
    1 2 10
    4 5 9
    5 1 3
    3 4 6
    2 4 1

    样例输出 1

    4
    NO

    样例输入 2

    1
    5 5 5
    1 2 
    2 3
    3 4
    4 5
    5 1
    1 2 100
    2 3 123
    4 3 1
    1 2 1
    2 3 1

    样例输出 2

    0
    NO

    样例输入 3

    1
    5 6 3
    1 2
    2 1
    1 3
    3 4
    4 5
    5 3
    1 3 5
    2 4 5
    3 5 999

    样例输出 3

    5
    YES

    提示

    【数据范围】

    对于30%的数据, 1<=n<=1000,1<=T<=5。          

    对于100%的数据,1<=n<=500000,1<=m<=100000,1<=k<=1000000 ,1<=x<=n,1<=y<=n,0<=z<=10000,1<=T<=5。

    保证m条双向边能够使所有城池交流畅通无阻。

    注:有兴趣的同学可以思考,如果每个帮派不把连接到外帮派的单向边拆毁,应该怎么做。(本次考试请根据题目描述做题)。


    来源  ht hjh