算法提高课汇总

模型抽象

• $n$个顶点$k$条边的无向边.

• 某个连接不视为回路, 回路长度大于$2$.

• 两个顶点最多一条连接: 不用考虑重边.

• 不存在连接同一顶点的连接: 不用考虑重边.

• 在不影响原图联通性的条件下, 去掉的边权最大. --> 留下的边权最小, 且仍保持原联通性.
  题目没有要求原图是联通的, 所以题目转化为求若干个独立联通块的对应最小生成树.

代码实现

• $Prim$算法从某个联通块出发, 逐步求出该连通块最小生成树.

• $Kruskal$算法是在保证没有回路的情况下加入最小边权. 算法本身没有要求最终图联通, 而只是保证在恰好无环的限制下加入尽可能多的最小边权.

所以本题用$Kruskal$求解更加容易(直接应用).

若原图联通, 可以认为$Kruskal$做到一半时得到的是若干独立的最小生成树.

$Kruskal\;m\lg(m)$

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, M = 210;

int n, m;
int p[N]; 
struct Edge
{
    int u, v, w;
    bool operator< (const Edge &edge) const
    {
        return w < edge.w;
    }
}e[M];

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

int find(int x)
{
    if( x != p[x] )
        return p[x] = find( p[x] );
    return p[x];
}

int kruskal()
{
    init(n);
    sort(e, e + m);

    int res = 0; //记录不能加入联通块的边权
    for( int i = 0; i < m; i ++ )
    {
        int u = find( e[i].u ), v = find( e[i].v ), w = e[i].w;
        if( u == v )    res += w;
        else p[u] = v; //加入连通块
    }
    return res;
}

int main()
{
    cin >> n >> m;
    for( int i = 0; i < m; i ++ )
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[i] = {u, v, w};
    }

    cout << kruskal() << endl;

    return 0;
}