算法提高课汇总

算法思路

先将必选边加入图中. 考虑最小生成树算法证明 $Kruskal$正确性证明中的短接操作:

• 将加入的必须选边短接, 忽略必选边顶点联通块中的非必选边. 则从剩下的可选边选择边权和最小即
  最小生成树问题. 通过$Kruskal$算法得到最小生成树后, 再将被短接的边“拉伸”回原来长度即得到
  问题的解.

可以认为$Kruskal$可以从一个已经工作到一半的图中继续找剩下可选边的最小边权和.

代码实现

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2010, M = 10010;

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)
{
    return p[x] == x ? p[x] : p[x] = find(p[x]);
}

void unit(int x, int y)
{//合并两个并查集
    x = find(x), y = find(y);
    p[x] = y;
}

bool same(int x, int y)
{//判断两个点是否属于同一并查集
    return find(x) == find(y);
}

int main()
{
    cin >> n >> m;

    init(n);
    int cnt = 0, res = 0;
    while( m -- )
    {
        int t, u, v, w;
        cin >> t >> u >> v >> w;
        if( t == 1 )
        {
            unit(u, v);
            res += w;
        }
        else
        {
            e[cnt ++] = {u, v, w};
        }
    }

    sort(e, e + cnt);
    for( int i = 0; i < cnt; i ++ )
    {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        if( !same(u, v) )
        {
            unit(u, v);
            res += w;
        }
    }
    cout << res << endl;

    return 0;
}