算法提高课汇总

模型抽象

• 最小联通花费, 且权值均为正数, 所以加入的边权一定是恰好联通 --> 最小生成树问题.
  (如果含负权, 则首先将所有负权边加入图中, 再用$Kruskal$加入恰好联通的最小正权边).

• 此时问题与AcWing 1143. 联络员相同:
  在一个已经加入部分边的图中, 让生成树最小. 可以通过$Kruskal$求解.

具体实现

• 因为纵向边权重均为$1$, 小于横向边权重$2$. 可以先加入纵向边再加入横向边, 省去排序过程.

• 已加入边可以不同于AcWing 1143. 联络员 — 特殊判断, 且不加入并查集; 而可以直接加入
  并查集统一处理. 因为加入并查集后顶点已经联通, 在$Kruskal$算法过程中会被pass. 另一个
  AcWing 1143. 联络员问题需要特殊考虑必加入边的原因是两个顶点可能有重边, 此时就不能
  pass了, 而是将所有必加重边全部加到答案中.

$Kruskal\;O(m)$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, M = N * N, E = 2 * M;

int n, m, k;
int ids[N][N]; //ids(x, y) = x * n + y. 将二维映射为一维
int p[M];
struct Edge
{
    int u, v, w;
}e[E];

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

int find(int x)
{
    return x == p[x] ? x : p[x] = find( p[x] );
}

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

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

void get_edges()
{//建图
    int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, dw[] = {1, 1, 2, 2}; //先纵再横
    for( int i = 0; i < 4; i ++ )
    {
        for( int x = 1; x <= n; x ++ )
        {
            for( int y = 1; y <= m; y ++ )
            {
                int nx = x + dx[i], ny = y + dy[i];
                if( 1 <= nx && nx <= n && 1 <= ny && ny <= m )
                {
                    int a = ids[x][y], b = ids[nx][ny];
                    if( a < b )
                    {//防止重复建边
                        e[k ++] = {a, b, dw[i]};
                    }
                }
            }
        }
    }
}

int kruskal()
{
    get_edges();
//  sort(e, e + k);
    int res = 0;
    for( int i = 0; i < k; i ++ )
    {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        if( !same(u, v) )
        {
            res += w;
            unit(u, v);
        }
    }
    return res;
}

int main()
{
    cin >> n >> m;
    for( int i = 1, t = 1; i <= n; i ++ )
        for( int j = 1; j <= m; j ++ )
            ids[i][j] = t ++;

    init(n * m); //初始化并查集
    int x1, y1, x2, y2;
    while( cin >> x1 >> y1 >> x2 >> y2 )
    {
        int a = ids[x1][y1], b = ids[x2][y2];
        unit(a, b);
    }

    cout << kruskal() << endl;

    return 0;
}