标题很长很吓人，以我本人的能力，只能水一水，看大佬们AK...
这次资格赛状况连连，在许多ACM群里纷纷吐槽，例如1004题意不明确，1002数据太弱，1001？？？
到了第二天才水过1002，惭愧惭愧。比赛结束后，写一个简要题解证明我来过（骗访问量???)。
Accepts: 674
Submissions: 6056
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 1 1 2 1 3 3 1 2 5 1 2 4 2 3 3 Sample Output 1 3题意如上。
思路：可以理解为给你n个点，m个边，和每条边的权值，如果原图不联通，则输出0，如果连通，则找出与其他顶点相连的所有边权值和最小的点即可。
标程应该是最小割？但是由于数据太弱，直接用一个cost数组记录权值和+并查集就水过，罪过罪过。
#define _CRT_SECURE_NO_WARNINGS //VS下用一些不符合标准的函数如scanf，需要声明这个宏 #include <iostream> #include <cstdio> #include <string> #include <algorithm> #include <queue> #include <string.h> using namespace std; const int MAXN = 3000 + 5; int cost[MAXN]; //记录每个顶点权值和 int pre[MAXN]; //前驱结点 int n, m; int getR(int x) { //并查集求根节点 while (x != pre[x]) x = pre[x]; return x; } void joint(int x,int y){ //合并 int xx = getR(x); int yy = getR(y); if (xx != yy) pre[xx] = yy; } int main() { while (~scanf("%d%d", &n, &m)) { memset(cost, 0, sizeof(cost)); for (int i = 1;i <= n;++i) pre[i] = i; for (int i = 1;i <= m;++i) { int src, dest, weight; scanf("%d%d%d", &src, &dest, &weight); if (src == dest) continue; //自环不用考虑 cost[src] += weight; cost[dest] += weight; joint(src, dest); } int cnt = 0; for (int i = 1;i <= n;++i) { if (pre[i] == i) //判断原图是否连通 cnt++; } if (cnt == 1) printf("%d\n", (sort(cost + 1, cost + 1 + n), cost[1])); //发现逗号运算符真的Coooool！ else printf("0\n"); } return 0; }
