【CF1095F】 Make It Connected（最小生成树）

题目链接

如果没有特殊边的话显然答案就是权值最小的点向其他所有点连边。

所以把特殊边和权值最小的点向其他点连的边丢一起跑最小生成树就行了。

#include <cstdio>

#include <algorithm>

using namespace std;

const int MAXN = 200010;

typedef long long ll;

inline ll read(){

    ll s = 0, w = 1;

    char ch = getchar();

    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); }

    while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); }

    return s * w;

}

struct Edge{

	int from, to;

	ll dis;

	int operator < (const Edge A) const{

		return dis < A.dis;

	}

}e[MAXN << 1];

int n, m, pos;

ll ans, w[MAXN], mn = 2147483647214748364ll;

int f[MAXN];

inline int find(int x){

	return f[x] == x ? x : f[x] = find(f[x]);

}

int main(){

	n = read(); m = read();

	for(int i = 1; i <= n; ++i){

		w[f[i] = i] = read();

		if(w[i] < mn) mn = w[i], pos = i;

	}

	for(int i = 1; i <= m; ++i){

		e[i].from = read();

		e[i].to = read();

		e[i].dis = read();

	}

	for(int i = 1; i <= n; ++i)

		e[i + m] = (i == pos) ? (Edge){ 0, 0, 2147483647214748364ll } : (Edge){ i, pos, w[i] + w[pos] };

	sort(e + 1, e + n + m + 1);

	for(int i = 1, k = n - 1; k; ++i)

		if(find(e[i].from) != find(e[i].to))

			f[find(e[i].from)] = find(e[i].to), --k, ans += e[i].dis;

	printf("%lld\n", ans);

	return 0;

}

巴特西

【CF1095F】 Make It Connected（最小生成树）

最新文章

热门文章