1, AcWing 1140 Shortest network

[Title Description]
Farmer John was elected mayor of his town!
One of his campaign promises is to build an Internet in the town and connect to all farms.
John has arranged a high-speed network line for his farm. He wants to share this line with other farms.
What's the number of John's farm 1 1 1. The number of other farms is 2 ∼ n 2∼n 2∼n.
In order to minimize the cost, he wants the total length of optical fiber used to connect all farms to be as short as possible.
You will get a list of connection distances between farms. You must find a solution that can connect all farms and minimize the optical fiber used.

[input format]
The first line contains an integer n n n. Indicates the number of farms.
next n n n rows, each containing n n n integers, enter one, all on the diagonal 0 0 Symmetric matrix of 0.
Among them x + 1 x+1 x+1 line y y The integer in the y column represents the connected farm x x x and farm y y y the required fiber length.

[output format]
Outputs an integer representing the minimum required fiber length.

[data range]
3 ≤ n ≤ 100 3≤n≤100 3≤n≤100
The distance between each two farms is a non negative integer and does not exceed 100000 100000 100000.

[input example]

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

[output example]

28

[analysis]

Template questions, as a review of the Prim algorithm~

[Code]

#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;
}

2, AcWing 1141 LAN

[Title Description]
In a LAN n n n computers and k k k two-way network cables. The number of the computer is 1 ∼ n 1∼n 1∼n. Due to the negligence of the staff when building the LAN, the connection in the LAN now forms a loop. We know that if the LAN forms a loop, the data will be transmitted continuously in the loop, resulting in the phenomenon of network card.

be careful:

• For a connection, although it is bidirectional, we do not treat it as a loop. The circuit described in this question must contain at least two different connections.
• There will be at most one connection between two computers.
• There is no connection. The two ends it connects are the same computer.

Because the network cable connecting the computer itself is different, some connections are not very smooth. We use it f ( i , j ) f(i,j) f(i,j) indicates i , j i,j i. J) the smoothness of the connection between, f ( i , j ) f(i,j) The smaller the value of f(i,j), it means i , j i,j i. The more unobstructed the connection between J.

Now we need to solve the loop problem. We will remove some connections so that there is no loop in the network and does not affect the connectivity (that is, if a certain two points are connected before, they must also be connected after removal), and the connection of the network cable will be removed Σ f ( i , j ) Σf(i,j) Σ f(i,j) is the maximum, and this maximum value is requested.

[input format]
Two positive integers in the first line n , k n,k n,k.
Next k k Three positive integers for each line of k i , j , m i,j,m i. J, M represents i , j i,j i. J there is network cable connection between the two computers, and the degree of smoothness is m m m.

[output format]
A positive integer indicating the number of network cables removed Σ f ( i , j ) Σf(i,j) Σ The maximum value of f(i,j).

[data range]
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

[input example]

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

[output example]

8

[analysis]

There may be multiple connected blocks in this problem. We need to remove the edge with the largest weight as possible without affecting the connectivity of each point in each connected block. The "need" of the generated forest is the minimum. When we do Kruskal algorithm, when the two endpoints of an edge have been connected, it indicates that the edge needs to be removed and r e s res res plus the weight of this edge.

[Code]

#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;//If x and y are not in a connected block, they are connected
        else res += e[i].w;//x and y are connected, indicating that this edge needs to be removed
    }
    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;
}