度度熊的王国战略

 

 Accepts: 644

 

 Submissions: 5880

 Time Limit: 40000/20000 MS (Java/Others)

 

 Memory Limit: 32768/132768 K (Java/Others)

Problem Description

度度熊国王率领着喵哈哈族的勇士，准备进攻哗啦啦族。

哗啦啦族是一个强悍的民族，里面有充满智慧的谋士，拥有无穷力量的战士。

所以这一场战争，将会十分艰难。

为了更好的进攻哗啦啦族，度度熊决定首先应该从内部瓦解哗啦啦族。

第一步就是应该使得哗啦啦族内部不能同心齐力，需要内部有间隙。

哗啦啦族一共有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 11 2 13 31 2 51 2 42 3 3

Sample Output

13 感觉是这次比赛最水的题了，竟然AC的不是最多。。因为是资格赛就做了一道。 受最近专题训练的影响，开始各种生成树、并查集思路，后来本着重(lai)在(hua)参(shui)与(de)的原则，贪心了一下竟然AC，数据太水不吐槽。。 贪心想法是直接记录与每个点相连边的权值和，取最小的删除（将一名将领隔离出来）。

#include
         
          #include
          
           #define MAX 3005#define INF 0x3f3f3f3fint 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]
          
         

不过也很容易举出反例： 4 4 1 2 3 1 3 10 2 4 11 3 4 4 程序输出13 而正解为7，因为删掉的两条边不相连。 希望比赛结束后，可以学习下神犇的正解orz。第一次参加百度之星~发个题解纪念一下。 yzm10到此一水 2017.8.6