算法提高课汇总

模型抽象

• 无向联通图, 交叉路口作为图中顶点, 且图中没有重边.

• 要求1: 选择边后生成的图是连通图.

• 要求2: 需要的边最小. 联通且边最小--> 生成树.

• 要求3: 生成树中最大边权最小.

二分算法

“最大边权最小”, 考虑用二分思路求解.

• 二分最大边权的长度$x$, 在判断当前图联通性时只能取权值小于$x$的边.

二分$+bfs \; O(m\lg(C))$

#include <cstring>
#include <iostream>

using namespace std;

const int N = 310, M = 8000 * 2 + 10, C = 10000;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int q[N]; bool st[N];//st[v]: v是否在队列中

void add(int u, int v, int c)
{
    e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = idx ++;
}

//bfs, x: 选取的边权最大值
bool bfs(int x)
{
    memset(st, 0, sizeof st);

    int hh = 0, tt = 0, cnt = 0; //cnt: 联通图中顶点个数
    q[tt ++] = 1;
    st[1] = true; 

    while( hh < tt ) 
    {
        int u = q[hh ++]; 
        cnt ++;

        for( int i = h[u]; ~i; i = ne[i] )
        {
            int v = e[i];
            if( !st[v] && w[i] <= x )
            {
                q[tt ++] = v;
                st[v] = true;
            }
        }
    }

    return cnt == n;
}

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

    memset(h, -1, sizeof h);
    while( m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    //二分
    int l = 1, r = C;
    while( l < r )
    {
        int mid = l + r >> 1;
        if( bfs(mid) )  r = mid;
        else    l = mid + 1;
    }
    cout << n - 1 << ' ' << l << endl;

    return 0;
}

$Kruskal$算法

因为$Kruskal$算法每次选取的是能够联通的且不构成回路(不加入多余边)的最小边权. 可以用反证法证明
若最优解第$k$条边选取的是$e_k$, 而没有选取$Kruskal$算法选取的边$e$. 用$e$替换$e_k$不会让最优解变大.

$Prim$从一点扩张, 而$Kruskal$显得更有大局观(格局hh), 每次选取的是整个图中可以选择的最小边权.

代码实现$O(m\lg(m))$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310, M = 8010;

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

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

    int res; //选择的最大权
    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 )
        {
            p[u] = v;
            res = w;
        }
    }
    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 << n - 1 << ' ';
    cout << kruskal() << endl;

    return 0;
}