【次小生成树】POJ 1679 The Unique MST
http://poj.org/problem?id=1679题意：问最小生成树是否唯一
思路：
用Kruskal先求最小生成树，结果即为min，把所用到的边记录下来（这里是记录的对应的下表），然后枚举这些边，
每次去掉一个边再求一次最小生成树，结果为tmin，如果能构成最小生成树tmin==min，则说明最小生成树不唯一
Sample Input
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
Sample Output
3
Not Unique!
代码自己YY吧……
#include <iostream>#include <fstream>#include <algorithm>#include <string>#include <set>//#include <map>#include <queue>#include <utility>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>//#include <ctime>#include <ctype.h>using namespace std;#define inf 0x3fffffffint n, k, pre, num, ind;struct road{int a, b;int weight;}r;bool cmp (road x, road y){return x.weight < y.weight;}int find (int a){while (a != pre)a = pre;return a;}int MST (int key){int mincost = 0, i, tp = 0, A, B;for (i = 1; i <= n; i++)pre = i;for (i = 0; i < k; i++){if (i == key)continue;A = find (r.a);B = find (r.b);if (A != B){if (key == -1)num = i;mincost += r.weight;pre = A;}}for (i = 1; i <= n; i++){if (pre == i){tp++;if (tp > 1)return inf;}}return mincost;}int main(){int m, t, i, a, b, w, mins, tmins, tp;scanf ("%d", &t);while (t--){k = ind = 0;scanf ("%d%d", &n, &m);while (m--){scanf ("%d%d%d", &a, &b, &w);r.a = a;r.b = b;r.weight = w;k++;}sort (r, r+k, cmp);mins = MST (-1);tmins = inf;for (i = 0; i < ind; i++){tp = MST (num);if (tmins > tp)tmins = tp;}if (tmins > mins)printf ("%d\n", mins);else puts ("Not Unique!");}return 0;}
页:
[1]