AcWing 1142. 繁忙的都市

题目传送门

一、Kruskal算法

#include 
using namespace std;

const int N = 310, M = 8010;
//记录边的结构体
//因为要不断的枚举边，所以用结构体就OK
struct Edge {
    int a, b, w;
} e[M];
bool operator<(const Edge &a, const Edge &b) {
    return a.w < b.w;
}
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 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;
            //可以直接写res = w(kruskal的性质)
            // res = max(res, w);
            res = w;
        }
    }
    cout << n - 1 << " " << res << endl;
    return 0;
}

二、二分+并查集

#include 
using namespace std;
const int N = 310, M = 8010;

//记录边的结构体
//因为要不断的枚举边，所以用结构体就OK
struct Edge {
    int a, b, w;
} e[M];
bool operator<(const Edge &a, const Edge &b) {
    return a.w < b.w;
}
int n, m; // n个节点,m条边

//并查集
int p[N];
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
//利用并查集判断联通块是否含有n个点
bool check(int maxC) {
    //初始化并查集 (1~n)
    for (int i = 1; i <= n; i++) p[i] = i;
    //合并
    for (int i = 0; i < m; i++) {
        int a = e[i].a, b = e[i].b, w = e[i].w;
        if (w > maxC) break; //一直枚举到有边的权值大于maxc为止
        a = find(a), b = find(b);
        if (a != b) p[a] = b;
    }
    //是不是都已经合并到一个集合中了
    int x = find(p[1]);
    for (int i = 2; i <= n; i++)
        if (find(i) != x) return false;
    return true;
}

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);

    int l = 1, r = 10010;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    //输出最后的解,在规定上限权值的情况下，找到最小生成树
    //最小生成树当然是n-1条边
    cout << n - 1 << ' ' << r << endl;
    return 0;
}

三、Prim算法

#include 
using namespace std;

const int N = 310;
int dist[N];
int g[N][N];
int n, m;
bool st[N];

int prim() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    int res = 0;
    for (int i = 0; i < n; i++) {
        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 = max(res, dist[t]);
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    cout << n - 1 << " " << prim() << endl;
    return 0;
}