prim求调,送大佬一关注
查看原帖
prim求调,送大佬一关注
819682
Exile_Code楼主2023/11/8 21:07
#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <string>
#include <cmath>
#include <bitset>
#include <stack>
#include <unordered_set>


#define ull				unsigned long long 
#define ll				long long
#define pii				pair<ll ,ll>
#define ft				first
#define sd				second
#define pr				pair
#define cy				cout<<"Yes"<<endl
#define cn				cout<<"No"<<endl
#define forn(i,n)		for(int (i)=0;(i)<(n);(i)++)   
#define forne(i,n)		for(int (i)=1;(i)<=(n);(i)++)
#define rforn(i,n)		for(int (i)=(n-1);(i)>=(0);(i)--)   
#define rforne(i,n)		for(int (i)=(n);(i)>=(1);(i)--)
#define vv				vector

struct edge {
	int next, to, w;
};
const int inf = 0x004f4f4f;
const int N = 5e5 + 10;
vv<vv<pii>>tree;
vv<vv<edge>>e;
ll t;

struct cmp {

	bool operator()(pr<int, pii>& a, pr<int, pii>& b) {

		return a.first < b.first;
	}

};


void solve() {


	int n, m; cin >> n >> m;
	e.resize(m);
	
	priority_queue<pii,vv<pii>,greater<pii>>q;
	tree.resize(n + 1, vv<pii>());
	bitset<1000000>flag;
	forn(i, n) {
		int a, b, c;
		cin >> a >> b >> c;
		
		tree[a].push_back({c,b});
		tree[b].push_back({c,a});
		
	}

	if (tree[1].size() == 0) {
		cout << "orz" << endl;
	}//第一个点不连通
	else
		q.push({ 0,1 });
	
	ll ans = 0;
	while (q.size()) {

		auto a = q.top();
		q.pop();
		if (flag[a.sd])//连过了
			continue;

		ans += a.ft;
		flag[a.sd] = 1;
		for (auto ret : tree[a.sd]) {//枚举出边
			if(!flag[ret.sd])
				q.push({ ret.ft,ret.sd });
		}
	}

	if (flag.count() != n)//没有连通n个点
		cout << "orz" << endl;
	else	
		cout << ans << endl;

}       

int main() {


	t = 1;
	//cin >> t;

	while (t--)
		solve();

	return 0;
}


2023/11/8 21:07
加载中...