忍界大战(war)
测试数据来自 wjszez/2219
【题目背景】
木叶忍者村是忍者世界中赫赫有名的强大村子,而它的繁荣离不开一位优秀的领导——火影。火影不仅需要拥有高超的战斗技巧,还需要冷静、决断和强大的统筹能力。而你,依靠AKIOI的惊人表现,被选举成为了新一任火影助理。
【题目描述】
忍者世界中爆发了世界大战,到处死伤惨重,整个木叶所剩无几的忍者分布在许多据点。据点之间有一些道路连接,由于战火纷飞,这些道路并不稠密。现在火影希望排一些忍者去守卫一些道路,使得所有据点都能通过这些道路互相到达。由于忍者是珍贵的,他希望派出最少的人。同时,这些道路的危险系数之和也要最小。
【输入格式】
第一行包含n和m,表示据点数量和道路数量
第二行开始的m行每行包含了u,v,w分别表示一条道路连接的两个据点和这条道路的危险系数。
【样例数据】
IN:
4 7
1 2 477
2 3 267
3 4 0
2 1 137
2 1 564
3 1 408
3 4 152
OUT:
404
【数据范围】
对于30%的数据n<=2000 m<=8000
对于60%的数据n<=10000 m<=20000
对于所有数据0<n<=30000 0<m<=50000
信息
- ID
- 2627
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者