Gym 100803F There is No Alternative（最小生成树）

Description

ICPC (Isles of Coral Park City) consist of several beautiful islands.

The citizens requested construction of bridges between islands to resolve inconveniences of using boats between islands, and they demand that all the islands should be reachable from any other islands via one or more bridges.

The city mayor selected a number of pairs of islands, and ordered a building company to estimate the costs to build bridges between the pairs. With this estimate, the mayor has to decide the set of bridges to build, minimizing the total construction cost.

However, it is difficult for him to select the most cost-efficient set of bridges among those connecting all the islands. For example, three sets of bridges connect all the islands for the Sample Input 1. The bridges in each set are expressed by bold edges in Figure F.1.

Figure F.1. Three sets of bridges connecting all the islands for Sample Input 1

As the first step, he decided to build only those bridges which are contained in all the sets of bridges to connect all the islands and minimize the cost. We refer to such bridges as no alternative bridges. In Figure F.2, no alternative bridges are drawn as thick edges for the Sample Input 1, 2 and 3.

Write a program that advises the mayor which bridges are no alternative bridges for the given input.

Input

The input consists of several tests case.

Figure F.2. No alternative bridges for Sample Input 1, 2 and 3

$$N \ M$$

$$S_1 \ D_1 \ C_1$$

$$S_M \ D_M \ C_M$$

For each test, the first line contains two positive integers N and M . N represents the number of islands and each island is identified by an integer 1 through N. M represents the number of the pairs of islands between which a bridge may be built.

Each line of the next M lines contains three integers Si, Di and Ci (1 ≤ i ≤ M) which represent that it will cost Ci to build the bridge between islands Si and Di. You may assume 3 ≤ N ≤ 500, N − 1 ≤ M ≤ min(50000, N(N − 1)/2), 1 ≤ Si < Di ≤ N, and 1 ≤ Ci ≤ 10000. No two bridges connect the same pair of two islands, that is, if i ≠ j and Si = Sj , then Di ≠ Dj. If all the candidate bridges are built, all the islands are reachable from any other islands via one or more bridges.

Output

Output two integers, which mean the number of no alternative bridges and the sum of their construction cost, separated by a space.

Sample Input

4 4
1 2 3
1 3 3
2 3 3
2 4 3

4 4
1 2 3
1 3 5
2 3 3
2 4 3

4 4
1 2 3
1 3 1
2 3 3
2 4 3

3 3
1 2 1
2 3 1
1 3 1

Sample Output

1 3
3 9
2 4
0 0

链接

https://vjudge.net/problem/Gym-100803F

题意

求一个图的所有最小生成树中都有的边及其权值和。

题解

使用Kruskal或者Prim都可以，先求得一个最小生成树(mst)，然后对求得的mst中的n-1条边进行遍历，每次去掉一条边，新得到的mst如果与原来不相等则该边符合要求。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 510;
const int maxm = 50010;
const int inf = 0x3f3f3f3f;
struct Edge
{
    int u, v, w;
}edge[maxm];

int n, m;
int F[maxn];
bool vis[maxm];

bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}

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

//int find(int x)
//{
//    return (x == F[x]) ? x : F[x] = find(F[x]);
//}

int find(int root)
{
    int tmp, son = root;
    while (root != F[root])
        root = F[root];
    while (son != root)
    {
        tmp = F[son];
        F[son] = root;
        son = tmp;
    }
    return root;
}

int kruskal(int k)
{
    init();
    int sum = 0, cnt = 0;
    for (int i = 0; i < m; ++i)
    {
        if (i == k) // 去掉该边
            continue;
        int fu = find(edge[i].u), fv = find(edge[i].v);
        if (fu != fv)
        {
            ++cnt;
            F[fu] = fv;
            sum += edge[i].w;
            vis[i] = true;
        }
        if (cnt == n - 1)
            break;
    }
    return sum;
}

int main()
{
    while (scanf("%d%d", &n, &m) != EOF)
    {
        for (int i = 0; i < m; ++i)
            scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
        memset(vis, 0, sizeof(vis));
        sort(edge, edge + m, cmp);
        int sum = kruskal(-1), tmp, cnt = 0, ans = 0;
        for (int i = 0; i < m; ++i)
        {
            if (vis[i]) // 对mst中的n-1条边进行遍历
            {
                tmp = kruskal(i);
                if (tmp != sum) // 与原mst不相等则符合要求
                {
                    cnt++;
                    ans += edge[i].w;
                }
            }
        }
        printf("%d %d\n", cnt, ans);
    }
    return 0;
}

并查集写的话还是非递归的路径压缩好使，实测快了将近100ms。

补充

The end.
2018-05-07 星期一