【算法题归纳合集】图论-最小生成树的典型应用

本文主要是介绍【算法题归纳合集】图论-最小生成树的典型应用，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、AcWing 1140. 最短网络

【题目描述】
农夫约翰被选为他们镇的镇长！
他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。
约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。
约翰的农场的编号是 1 1 1，其他农场的编号是 2 ∼ n 2∼n 2∼n。
为了使花费最少，他希望用于连接所有的农场的光纤总长度尽可能短。
你将得到一份各农场之间连接距离的列表，你必须找出能连接所有农场并使所用光纤最短的方案。

【输入格式】
第一行包含一个整数 n n n，表示农场个数。
接下来 n n n行，每行包含 n n n个整数，输入一个对角线上全是 0 0 0的对称矩阵。
其中第 x + 1 x+1 x+1行 y y y列的整数表示连接农场 x x x和农场 y y y所需要的光纤长度。

【输出格式】
输出一个整数，表示所需的最小光纤长度。

【数据范围】
3 ≤ n ≤ 100 3≤n≤100 3≤n≤100
每两个农场间的距离均是非负整数且不超过 100000 100000 100000。

【输入样例】

4
0  4  9  21
4  0  8  17
9  8  0  16
21 17 16  0

【输出样例】

28

【分析】

模板题，当做复习一下Prim算法~

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 110;
int g[N][N];
int st[N], dis[N];
int n;

int prim()
{
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (!~t || dis[j] < dis[t])) t = j;
        res += dis[t];
        st[t] = 1;
        for (int j = 1; j <= n; j++) dis[j] = min(dis[j], g[t][j]);
    }
    return res;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> g[i][j];
    cout << prim() << endl;
    return 0;
}

二、AcWing 1141. 局域网

【题目描述】
某个局域网内有 n n n台计算机和 k k k条 双向 网线，计算机的编号是 1 ∼ n 1∼n 1∼n。由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。

注意：

• 对于某一个连接，虽然它是双向的，但我们不将其当做回路。本题中所描述的回路至少要包含两条不同的连接。
• 两台计算机之间最多只会存在一条连接。
• 不存在一条连接，它所连接的两端是同一台计算机。

因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用 f ( i , j ) f(i,j) f(i,j)表示 i , j i,j i,j之间连接的畅通程度， f ( i , j ) f(i,j) f(i,j)值越小表示 i , j i,j i,j之间连接越通畅。

现在我们需要解决回路问题，我们将除去一些连线，使得网络中没有回路且不影响连通性（即如果之前某两个点是连通的，去完之后也必须是连通的），并且被除去网线的 Σ f ( i , j ) Σf(i,j) Σf(i,j)最大，请求出这个最大值。

【输入格式】
第一行两个正整数 n , k n,k n,k。
接下来的 k k k行每行三个正整数 i , j , m i,j,m i,j,m表示 i , j i,j i,j两台计算机之间有网线联通，通畅程度为 m m m。

【输出格式】
一个正整数，表示被除去网线的 Σ f ( i , j ) Σf(i,j) Σf(i,j)的最大值。

【数据范围】
1 ≤ n ≤ 100 1≤n≤100 1≤n≤100
0 ≤ k ≤ 200 0≤k≤200 0≤k≤200
1 ≤ f ( i , j ) ≤ 1000 1≤f(i,j)≤1000 1≤f(i,j)≤1000

【输入样例】

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

【输出样例】

8

【分析】

本题可能存在多个连通块，需要我们去掉权值尽可能大的边，且不影响每个连通块内各点的连通性。即需要求出最小的“生成森林”。我们在做Kruskal算法时，当某条边的两个端点已经被连通时，说明该边需要去除，将 r e s res res加上这条边的权值即可。

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 110, M = 210;
int pre[N];
int n, m;

struct Edge
{
    int x, y, w;
    bool operator< (const Edge& t) const
    {
        return w < t.w;
    }
}e[M];

int find(int k)
{
    if (pre[k] == k) return k;
    return pre[k] = find(pre[k]);
}

int kruskal()
{
    sort(e, e + m);
    int res = 0;
    for (int i = 0; i < m; i++)
    {
        int px = find(e[i].x), py = find(e[i].y);
        if (px != py) pre[px] = py;//x与y不在一个连通块中则连接
        else res += e[i].w;//x与y已经连通了说明这条边需要去掉
    }
    return res;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) pre[i] = i;
    for (int i = 0; i < m; i++) cin >> e[i].x >> e[i].y >> e[i].w;
    cout << kruskal() << endl;
    return 0;
}

这篇关于【算法题归纳合集】图论-最小生成树的典型应用的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！