度度熊国王率领着喵哈哈族的勇士，准备进攻哗啦啦族。
哗啦啦族是一个强悍的民族，里面有充满智慧的谋士，拥有无穷力量的战士。
所以这一场战争，将会十分艰难。
为了更好的进攻哗啦啦族，度度熊决定首先应该从内部瓦解哗啦啦族。
第一步就是应该使得哗啦啦族内部不能同心齐力，需要内部有间隙。
哗啦啦族一共有n个将领，他们一共有m个强关系，摧毁每一个强关系都需要一定的代价。
现在度度熊命令你需要摧毁一些强关系，使得内部的将领，不能通过这些强关系，连成一个完整的连通块，以保证战争的顺利进行。
请问最少应该付出多少的代价。
Input本题包含若干组测试数据。
第一行两个整数n，m，表示有n个将领，m个关系。
接下来m行，每行三个整数u,v,w。表示u将领和v将领之间存在一个强关系，摧毁这个强关系需要代价w
数据范围：
2<=n<=3000
1<=m<=100000
1<=u,v<=n
1<=w<=1000
Output对于每组测试数据，输出最小需要的代价。
Sample Input 2 1 1 2 1 3 3 1 2 5 1 2 4 2 3 3 Sample Output 1 3感觉是这次比赛最水的题了，竟然AC的不是最多。。因为是资格赛就做了一道。受最近专题训练的影响，开始各种生成树、并查集思路，后来本着重(lai)在(hua)参(shui)与(de)的原则，贪心了一下竟然AC，数据太水不吐槽。。贪心想法是直接记录与每个点相连边的权值和，取最小的删除（将一名将领隔离出来）。 #include<stdio.h> #include<string.h> #define MAX 3005 #define INF 0x3f3f3f3f int dj[MAX]; int main() { int n,m,u,v,w,i; while(~scanf("%d%d",&n,&m)){ memset(dj,0,sizeof(dj)); for(i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&w); if(u!=v){ dj[u]+=w; dj[v]+=w; } } int min=INF; for(i=1;i<=n;i++){ if(dj[i]<min) min=dj[i]; } printf("%d\n",min); } return 0; } View Code 不过也很容易举出反例：4 41 2 31 3 102 4 113 4 4程序输出13 而正解为7，因为删掉的两条边不相连。希望比赛结束后，可以学习下神犇的正解orz。第一次参加百度之星~发个题解纪念一下。yzm10到此一水 2017.8.6
转载于:https://www.cnblogs.com/yzm10/p/7296559.html
相关资源：数据结构—成绩单生成器