Luogu-[图论2-3]-最小生成树

题单链接

P3366 [模板][最小生成树]

思路

模板题而已

AC Code

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5010, M = 200010;
struct Edge{
    int a, b, w;
    bool operator < (const Edge& e) const{
        return w < e.w;
    }
}e[M];
int p[N];
int n, m;

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

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

/*
 4 5
 1 2 2
 1 3 2
 1 4 3
 2 3 4
 3 4 3

 7
 */

P2872 USACO07DEC Building Roads S

思路

如果 $i,j$ 之间有边，则设权重为 $0$, 否则计算出边权，然后MST算法。比较坑的地方在求欧氏距离的时候，$dx dx + dy dy$可能 int 溢出，所以需要转换成 long long 或者double。

AC Code

#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef struct Edge{
    int a, b;
    double w;
    bool operator < (const Edge& e){
        return w < e.w;
    }
}e;
const int N = 1010;
PII q[N];
int p[N];
int n, m;
bool st[N][N];
vector<e> vece;

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

double get_dist(PII a, PII b){
    ll dx = a.x - b.x;
    ll dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> q[i].x >> q[i].y;
    for(int i = 1; i <= n; i++) p[i] = i;
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        vece.push_back({a, b, 0});
        st[a][b] = st[b][a] = true;
    }

    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            if(st[i][j]) continue;
            else{
                vece.push_back({i, j, get_dist(q[i], q[j])});
                st[i][j] = st[j][i] = true;
            }
        }
    }

    sort(vece.begin(), vece.end());
    double res = 0;
    for(auto e : vece){
        int a = find(e.a), b = find(e.b);
        if(a != b){
            p[a] = b;
            res += e.w;
        }
    }
    printf("%.2lf\n", res);

    return 0;
}

/*
 4 1
 1 1
 3 1
 2 3
 4 3
 1 4

 4.00
 */

可能溢出的一组数据:

in:输入

out:输出

P1991 无线通讯网

思路

根据坐标建图，然后MST，只需要在连通分量树 $cnt \leq k$ 时即可，k为卫星电话数，res为记录中的最小值。

原理很好理解，连通分量随加边而减少，且边权递减，因此序列性保证了答案的正确性。

AC Code

#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef struct Edge{
    int a, b;
    double w;
    bool operator < (const Edge& e){
        return w < e.w;
    }
}e;
const int N = 510;
PII q[N];
int p[N];
int n, m;
vector<e> vece;

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

double get_dist(PII a, PII b){
    ll dx = a.x - b.x;
    ll dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

int main(){
    cin >> m >> n;
    for(int i = 1; i <= n; i++) cin >> q[i].x >> q[i].y;
    for(int i = 1; i <= n; i++) p[i] = i;
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            vece.push_back({i, j, get_dist(q[i], q[j])});
        }
    }

    sort(vece.begin(), vece.end());
    double res = 0;
    int cnt = n;
    for(auto e : vece){
        if(cnt <= m) break;
        int a = find(e.a), b = find(e.b);
        if(a != b){
            p[a] = b;
            res = e.w;
            cnt--;
        }
    }
    printf("%.2lf\n", res);

    return 0;
}

/*
 2 4
 0 100
 0 300
 0 600
 150 750

 212.13
 */

P1967 [NOIP2013 提高组] 货车运输

思路

AC Code

P4047 [JSOI2010] 部落划分

思路

暴力存边，MST直到连通分量数为k，然后继续MST，第一个连接两个不同分量的边对应的权值即为答案。

二分以后补充

AC Code

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

#define x first
#define y second

typedef pair<int,int> PII;
const int N = 1010;
struct Edge{
    int a, b;
    double w;
    bool operator < (const Edge& e) const{
        return w < e.w;
    }
}e[N * N];
int p[N];
PII q[N];
int n, k, t;

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

double get_dist(PII a, PII b){
    int dx = a.x - b.x;
    int dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> q[i].x >> q[i].y;
    }
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            e[t++] = {i, j, get_dist(q[i], q[j])};
        }
    }

    sort(e, e + t);
    for(int i = 1; i <= n; i++) p[i] = i;

    int cnt = n;
    int i = 0;
    for(; i < t; i++){
        int a = find(e[i].a), b = find(e[i].b);
        if(a != b){
            p[a] = b;
            cnt--;
        }
        if(cnt <= k) break;
    }

    double res;
    for(; i < t; i++){
        int a = find(e[i].a), b = find(e[i].b);
        if(a != b){
            res = e[i].w;
            break;
        }
    }
    printf("%.2lf", res);
    return 0;
}

/*
 4 2
 0 0
 0 1
 1 1
 1 0

 1.00
 */

P1396 营救

思路

正常的MST求解，当s,t联通时退出

当然二分最短路应该也可以。

AC Code

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20010;
struct Edge{
    int a, b, w;
    bool operator < (const Edge& e){
        return w < e.w;
    }
}e[N];
int p[N];
int n, m, s, t;

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

int main(){
    cin >> n >> m >> s >> t;
    for(int i = 0; i < m; i++){
        int a, b, w;
        cin >> a >> b >> w;
        e[i] = {a, b, w};
    }

    sort(e, e + m);
    for(int i = 1; i <= n; i++) p[i] = i;

    int res = 0;
    for(int i = 0; i < m; i++){
        int a = find(e[i].a), b = find(e[i].b);
        if(find(s) == find(t)) break;
        if(a != b){
            p[a] = b;
            res = e[i].w;
        }
    }
    cout << res << endl;
    return 0;
}

/*
 3 3 1 3
 1 2 2
 2 3 1
 1 3 3

 2
 */

P2121 拆地毯

思路

等价于最大生成树中的前k个边

AC Code

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
struct Edge{
    int a, b, w;
    bool operator < (const Edge& e){
        return w > e.w;
    }
}e[N];
int p[N];
int n, m, k;

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

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

    sort(e, e + m);
    for(int i = 1; i <= n; i++) p[i] = i;
    int res = 0;
    for(int i = 0; i < m; i++){
        if(k <= 0) break;
        int a = find(e[i].a), b = find(e[i].b);
        if(a != b){
            p[a] = b;
            res += e[i].w;
            k--;
        }
    }
    cout << res << endl;
    return 0;
}

/*
 5 4 3
 1 2 10
 1 3 9
 2 3 7
 4 5 3

 22
 */

P1194 买礼物

思路

超级源点，建立源点0和其他点之间的边，e[0, i] = A然后跑 MST即可。

AC Code

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510;
struct Edge{
    int a, b, w;
    bool operator < (const Edge& e){
        return w < e.w;
    }
}e[N * N];
int p[N], g[N][N];
int n, m, t;

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

int main(){
    cin >> m >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> g[i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        e[t++] = {0, i, m};
    }
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            if(g[i][j] != 0) e[t++] = {i, j, g[i][j]};
        }
    }

    sort(e, e + t);
    for(int i = 0; i <= n; i++) p[i] = i;
    int res = 0;
    for(int i = 0; i < t; i++){
        int a = find(e[i].a), b = find(e[i].b);
        if(a != b){
            p[a] = b;
            res += e[i].w;
        }
    }
    cout << res << endl;
    return 0;
}

/*
 3 3
 0 2 4
 2 0 2
 4 2 0

 7
 */

P1195 口袋的天空

思路

MST每一次merge的时候连通分量减1，初始为n，即将连通分量减少到k即可。

如果可以，则输出权值和，否则连通分量＞0，则“No Answer”。

AC Code

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, M = 10010;
struct Edge{
    int a, b, w;
    bool operator < (const Edge& e){
        return w < e.w;
    }
}e[M];
int p[N];
int n, m, k;

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

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

    sort(e, e + m);
    for(int i = 1; i <= n; i++) p[i] = i;

    int res = 0, cnt = n;
    for(int i = 0; i < m; i++){
        int a = find(e[i].a), b = find(e[i].b);
        if(cnt <= k) break;
        if(a != b){
            p[a] = b;
            res += e[i].w;
            cnt--;
        }
    }
    if(cnt <= k) cout << res << endl;
    else cout << "No Answer" << endl;
    return 0;
}

/*
 3 1 2
 1 2 1

 1
 */

P4180 [BJWC2010] 严格次小生成树

思路

AC Code