修路方案（次小生成树）

修路方案

时间限制：3000 ms  |  内存限制：65535 KB

难度：5

 

描述

南将军率领着许多部队，它们分别驻扎在N个不同的城市里，这些城市分别编号1~N，由于交通不太便利，南将军准备修路。

现在已经知道哪些城市之间可以修路，如果修路，花费是多少。

现在，军师小工已经找到了一种修路的方案，能够使各个城市都联通起来，而且花费最少。

但是，南将军说，这个修路方案所拼成的图案很不吉利，想让小工计算一下是否存在另外一种方案花费和刚才的方案一样，现在你来帮小工写一个程序算一下吧。

 

输入

第一行输入一个整数T(1<T<20)，表示测试数据的组数
每组测试数据的第一行是两个整数V,E，(3<V<500,10<E<200000)分别表示城市的个数和城市之间路的条数。数据保证所有的城市都有路相连。
随后的E行，每行有三个数字A B L，表示A号城市与B号城市之间修路花费为L。

输出

对于每组测试数据输出Yes或No（如果存在两种以上的最小花费方案则输出Yes,如果最小花费的方案只有一种，则输出No)

样例输入

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

样例输出

No
Yes

 

      思路：

      次小生成树。记得判断删去后是否连通即可，也可以用 dp 方法求解。

 

      AC：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef struct {
    int a, b, num;
} node;

node no[200005];
int root[505], path[505];
int n, m, cnt, sum;

void init() {
    for (int i = 1; i <= n; ++i)
        root[i] = i;
}

int Find (int x) {
    return x == root[x] ? x : root[x] = Find(root[x]);
}

bool cmp (node a, node b) { return a.num < b.num; }

bool test() {
    int num = 0;
    for (int i = 1; i <= n; ++i) {
        if (root[i] == i) ++num;
        if (num > 1) return false;
    }

    return true;
}

bool solve () {
    if (!test()) return false;

    for (int i = 0; i < cnt; ++i) {
        init();

        int ans = 0;
        for (int j = 0; j < m; ++j) {
            if (j == path[i]) continue;

            int A = Find(no[j].a);
            int B = Find(no[j].b);
            if (A != B) {
                ans += no[j].num;
                root[A] = B;
            }
        }
        if (!test()) continue;

        if (ans == sum) return false;
    }

    return true;
}

int main() {

    int t;
    scanf("%d", &t);

    while (t--) {
        scanf("%d%d", &n, &m);


        for (int i = 0; i < m; ++i) {
            scanf("%d%d%d", &no[i].a, &no[i].b, &no[i].num);
        }

        sort(no, no + m, cmp);

        init();
        cnt = sum = 0;
        for (int i = 0; i < m; ++i) {
            int A = Find(no[i].a);
            int B = Find(no[i].b);
            if (A != B) {
                root[A] = B;
                path[cnt++] = i;
                sum += no[i].num;
            }
        }

        if (solve()) printf("No\n");
        else printf("Yes\n");

    }

    return 0;
}