手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

【ACWing】1143. 联络员

时间:2021/4/25 3:34:19|来源:|点击: 次

题目地址:

https://www.acwing.com/problem/content/1145/

Tyvj已经一岁了,网站也由最初的几个用户增加到了上万个用户,随着Tyvj网站的逐步壮大,管理员的数目也越来越多,现在你身为Tyvj管理层的联络员,希望你找到一些通信渠道,使得管理员两两都可以联络(直接或者是间接都可以)。本题中所涉及的通信渠道都是双向的。Tyvj是一个公益性的网站,没有过多的利润,所以你要尽可能的使费用少才可以。目前你已经知道,Tyvj的通信渠道分为两大类,一类是必选通信渠道,无论价格多少,你都需要把所有的都选择上;还有一类是选择性的通信渠道,你可以从中挑选一些作为最终管理员联络的通信渠道。数据保证给出的通信渠道可以让所有的管理员联通。注意:对于某两个管理员 u , v u,v u,v,他们之间可能存在多条通信渠道,你的程序应该累加所有 u , v u,v u,v之间的必选通行渠道。

输入格式:
第一行两个整数 n n n m m m表示Tyvj一共有 n n n个管理员,有 m m m个通信渠道;第二行到 m + 1 m+1 m+1行,每行四个非负整数, p , u , v , w p,u,v,w p,u,v,w p = 1 p=1 p=1时,表示这个通信渠道为必选通信渠道;当 p = 2 p=2 p=2时,表示这个通信渠道为选择性通信渠道; u , v , w u,v,w u,v,w表示本条信息描述的是 u u u v v v管理员之间的通信渠道, u u u可以收到 v v v的信息, v v v也可以收到 u u u的信息, w w w表示费用。

输出格式:
一个整数,表示最小的通信费用。

数据范围:
1 ≤ n ≤ 2000 1≤n≤2000 1n2000
1 ≤ m ≤ 10000 1≤m≤10000 1m10000

其实就是给定一个无向连通图之后,规定某些边必选的情况下,求一棵最小生成树。可以用Kruskal算法,先把必选边选上,然后将其余边按边权从小到大排序,如果当前边的两个点不连通则选该边,否则略过。算法正确性可以这样看,将必选边选好之后,整个图被分为了若干连通块,可以把这些连通块看成是若干个点,那么在剩余边里要选择的边,要使得所有点连通,事实上就是在做最小生成树。所以Kruskal算法在这个问题里也是正确的。代码如下:

#include <iostream>
#include <algorithm>
using namespace std;

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

int find(int x) {
    if (x != p[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, cnt = 0;
    for (int i = 0; i < m; i++) {
        int t, a, b, w;
        cin >> t >> a >> b >> w;
        // 如果是必选边,则选之,累加长度;否则把这条边存起来
        if (t == 1) {
            res += w;
            p[find(a)] = find(b);
        } else e[cnt++] = {a, b, w};
    }

    sort(e, e + cnt);

    for (int i = 0; i < cnt; i++) {
        int pa = find(e[i].a), pb = find(e[i].b);
        if (pa != pb) {
            p[pa] = pb;
            res += e[i].w;
        }
    }

    cout << res << endl;

    return 0;
}

时间复杂度 O ( m log ⁡ m ) O(m\log m) O(mlogm),空间 O ( n ) O(n) O(n)

上一篇:机器的终极智能 下一篇:static修饰符

Copyright © 2002-2019 某某自媒体运营 版权所有