NYOJ - 沟通无限校园网(最小生成树)

题目链接:http://nyoj.top/problem/1403

• 内存限制:64MB 时间限制:1000ms

题目描述:

校园网是为学校师生提供资源共享、信息交流和协同工作的计算机网络。校园网是一个宽带、具有交互功能和专业性很强的局域网络。如果一所学校包括多个学院及部门，也可以形成多个局域网络，并通过有线或无线方式连接起来。原来的网络系统只局限于以学院、图书馆为单位的局域网，不能形成集中管理以及各种资源的共享，个别学院还远离大学本部，这些情况严重地阻碍了整个学校的网络化需求。
无向连通图G=（V，E）来表示通信网络，V表示顶点集，E表示边集。把各个单位抽象为图中的顶点，顶点与顶点之间的边表示单位之间的通信网络，边的权值表示布线的费用。如果两个节点之间没有连线，代表这两个单位之间不能布线，费用为无穷大。现在需要设计网络电缆布线，将各个单位的局域网络连通起来，如何设计能够使费用最少呢？

输入描述:

第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是两个整数n,c(1<n,c<1000)表示该测试数据有n个顶点c条边。
随后的c行，每行有3个正整数u,v,w(0<u,v<=n, 0<w<10000),分别表示边的两个顶点编号u,v及两顶点之间的费用。

输出描述:

对于每一组输入，输出最小费用值。
每组的输出占一行。

样例输入:

2
7 12
1 2 23
1 6 28
1 7 36
2 3 20
2 7 1
3 4 15
3 7 4
4 5 3
4 7 9
5 6 17
5 7 16
6 7 25
4 6
1 2 10
1 4 5
1 3 8
2 3 8
2 4 11
3 4 8

样例输出:

57
21

解题思路:

模板题，直接套模板就行了，要注意当两个单位不能布线的时候，输出0.
下面是最常见的两种求最小生成树的算法:
Kruskal算法:

#include <iostream>
#include <algorithm>
using namespace std;
struct edge {
    int u, v, w;
}e[10010];
int f[1010];
bool cmp(edge A, edge B)
{
    return A.w < B.w;
}
int getf(int v)
{
    if (f[v] != v)
        return f[v] = getf(f[v]);
    return v;
}
bool merge(int u, int v)
{
    int t1 = getf(u);
    int t2 = getf(v);
    if (t1 != t2)
    {
        f[t2] = t1;
        return true;;
    }
    return false;
}
int Kruskal(int n, int m)
{
    int counts = 0, ans = 0;
    for (int i = 0; i < m; i++)
    {
        if (merge(e[i].u, e[i].v))
        {
            counts++;
            ans += e[i].w;
            if (counts == n - 1)
                return ans;
        }
    }
    return 0;
}
int main()
{
    int t, n, m;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            f[i] = i;
        for (int i = 0; i < m; i++)
            scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
        sort(e, e + m, cmp);
        printf("%d\n", Kruskal(n, m));
    }
    return 0;
}

prim算法: 

#include <stdio.h>
#include <string.h>
#define N 1020
const int inf = 99999999;
int e[N][N], dis[N], vis[N];
int main()
{
    int t, n, m, u, v, w, sum, minn, counts;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (i != j)
                    e[i][j] = inf;
        for (int i = 0; i < m; i++)
        {
            scanf("%d%d%d", &u, &v, &w);
            if (e[u][v] > w)
                e[u][v] = e[v][u] = w;
        }
        for (int i = 1; i <= n; i++)
        {
            dis[i] = inf;
            vis[i] = 0;
        }
        dis[1]=0;
        sum = counts = 0;
        while (counts < n)
        {
            minn = inf;
            for (int j = 1; j <= n; j++)
            {
                if (dis[j] < minn && !vis[j])
                {
                    minn = dis[j];
                    u = j;
                }
            }
            counts++;
            vis[u] = 1;
            sum += minn;
            for (v = 1; v <= n; v++)
                if (e[u][v] < inf)
                    if (!vis[v] && dis[v] > e[u][v])
                        dis[v] = e[u][v];
        }
        if (sum < inf)
            printf("%d\n", sum);
        else printf("0\n");
    }
    return 0;
}