最小生成樹(shù)

AcWing 1140. 最短網(wǎng)絡(luò)

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int w[N][N];
int dist[N];
bool st[N];
int n;

int prime()
{
    int res = 0;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    //和dj一樣 這里1號(hào)節(jié)點(diǎn)雖然是最短的，但是我們需要它去更新其他邊，因此不能st[1] = true;
    for (int i = 0; i < n; i ++ )//和dj一樣，這里循環(huán)n次才能把n個(gè)節(jié)點(diǎn)加進(jìn)最小生成樹(shù)
    {
        int t = -1;
        
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
                
        st[t] = true;
        res += dist[t];
        
        for (int j = 1; j <= n; j ++ )
        {
            dist[j] = min(dist[j], w[t][j]);//這里不用dist[t] + w[t][j],這是求一個(gè)點(diǎn)到一個(gè)集合的距離，后者是求點(diǎn)j到源點(diǎn)的距離
        }
    }
    return res;
}

int main ()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )//題目要的答案和節(jié)點(diǎn)的下標(biāo)無(wú)關(guān)，這里能把它存下來(lái)就行了
        for (int j = 1; j <= n; j ++ )
            cin >> w[i][j];
    
    cout << prime();
    return 0;
}

AcWing 1141. 局域網(wǎng)

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

using namespace std;

const int N = 110, M = 210;

struct Edge
{
    int a, b, w;
    bool operator < (const Edge &t)const
    {
        return w < t.w;
    }
}e[M];

int p[N];//并查集父類數(shù)組
int n, m;

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];//return x 也是一樣的
}
int main ()
{
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) p[i] = i;//并查集初始化（這個(gè)經(jīng)常忘），這個(gè)下標(biāo)i是有意義的，要根據(jù)題目給的節(jié)點(diǎn)編號(hào)來(lái)
    
    for (int i = 0; i < m; i ++ )
    {
        int a, b, w;
        cin >> a >> b >> w;
        //e[i].a = a, e[i].b = b, e[i].w = w;
        e[i] = {a, b, w};
    }
    
    sort(e, e + m);
    int res = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = find(e[i].a), b = find(e[i].b), w = e[i].w;//后面不用再find了，因?yàn)槲覀僡,b在定義的時(shí)候就是他們所屬的集合
    
        if(a != b) p[a] = b;
        else res += w;
    }
    
    cout << res;
    return 0;
}

AcWing 1142. 繁忙的都市

和上題一摸一樣，但是題意要求的out看起來(lái)需要特別處理，其實(shí)只要想清楚kruskal的性質(zhì)就好

//kruskal本身就具有選擇的路的權(quán)值中最大的權(quán)值盡量小這個(gè)性質(zhì)，因?yàn)槲覀冞吺桥判蛄说?/span>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310, M = 8010;

struct Edge
{
    int a, b, w;
    bool operator < (struct Edge &t)
    {
        return w < t.w;
    }
}e[M];

int n, m;
int p[N];

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

int main ()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    
    for (int i = 0; i < m; i ++ )
    {
        int a, b, w;
        cin >> a >> b >> w;
        e[i] = {a, b, w};
    }
    
    sort(e, e + m);
    int cnt = 0, res = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
        
        if (a != b) 
        {
            p[a] = b;
            cnt ++ ;
            res = w;
        }
    }
    
    cout << cnt << " " << res ;
    return 0;
}

AcWing 1143. 聯(lián)絡(luò)員

//1.用到了縮點(diǎn),但本題的是無(wú)形中的，一個(gè)聯(lián)通塊的縮成了它的父節(jié)點(diǎn)
//2.知道了kurskal有多牛，可以解決已經(jīng)有一些邊的最小生成樹(shù)問(wèn)題，也可以解決只找一部分邊的最小生成樹(shù)的問(wèn)題
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010, M = 10010;

struct Edge
{
    int a, b, w;
    bool operator < (struct Edge & t)
    {
        return w < t.w;
    }
}e[M];

int p[N];
int n, m;

int find (int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main ()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    
    int res = 0, k = 0;
    
    for (int i = 0; i < m; i ++ ) 
    {
        int t, a, b, w;
        cin >> t >> a >> b >> w;
        if (t == 1)
        {
            p[find(a)] = find(b);//先建立必須要選擇的邊
            res += w;
        }
        else 
        {
            e[k ++ ] = {a, b, w};//不是必須要選擇的再加入e數(shù)組
        }
    }
    
    sort(e, e + k);
    for (int i = 0; i < k; i ++ )
    {
        int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
        if (a != b)
        {
            p[a] = b;
            res += w;
        }
    }
    cout << res;
    return 0;
}

AcWing 1144. 連接格點(diǎn)

題意就是求最小生成樹(shù)，因?yàn)檫厵?quán)都是正數(shù)，那么我們多選一條邊必然會(huì)導(dǎo)致我們的代價(jià)增大
但如果題目說(shuō)了邊權(quán)為正或者負(fù)數(shù)，那么就不是最小生成樹(shù)了，極端一點(diǎn)所有邊都是負(fù)的，那么我們?yōu)榱舜鷥r(jià)最小肯定是所有邊都選文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-596764.html

//有點(diǎn)類似于拯救大兵那題
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e3 + 10, M = N * N, K = 2 * N * N;//M：點(diǎn)數(shù)， K = 邊數(shù)

struct  Edge
{
    int a, b, w;
}e[K];
int p[M];
int ids[N][N], cnt;//將二維坐標(biāo)映射成1維
int n, m, k;

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

void get_edges()
{
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}, dw[4] = {1, 2, 1, 2};//必須要按1212的順序枚舉，這樣u%2的時(shí)候就可以先添加1的邊再添加2的邊，自己排序少一個(gè)快排logn的復(fù)雜度
    for (int z = 0; z < 2; z ++ )//先枚舉u%2余數(shù)為0的再枚舉u%2余數(shù)為1的，余數(shù)為0說(shuō)明是豎邊權(quán)值為1，為1說(shuō)明是橫邊權(quán)值為2
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                for (int u = 0; u < 4; u ++ )
                {
                    if (u % 2 == z)
                    {
                        int x = i + dx[u], y = j + dy[u], w = dw[u];
                        int a = ids[i][j], b = ids[x][y];
                        if (a < b) e[k ++ ] = {a, b, w};//因?yàn)槭菬o(wú)向邊我們枚舉一個(gè)就行了
                    }
                }
}
int main()
{
    cin >> n >> m;
    
    for (int i = 1; i <= n * m; i ++ ) p[i] = i;
    
    for (int i = 1;i <= n; i ++ )//將二維坐標(biāo)映射成1維
        for (int j = 1; j <= m; j ++ )
            ids[i][j] = ++ cnt;
    
    int x1, x2, y1, y2;
    while(cin >> x1 >> y1 >> x2 >> y2)
    {
        int a = ids[x1][y1], b = ids[x2][y2];
        p[find(a)] = find(b);
    }
    
    get_edges();//初始化e[]
    
    
    int res = 0;
    for (int i = 0; i < k; i ++ )
    {
        int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
        if (a != b)
        {
            p[a] = b;
            res += w;
        }
    }
    
    cout << res;
    
    return 0;
    
}

到了這里，關(guān)于算法提高-圖論- 最小生成樹(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！