cnt为什么不是在成功插入一个点时再统计
查看原帖
cnt为什么不是在成功插入一个点时再统计
800543
NirvanaCeleste楼主2024/10/23 22:00
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200020;
int n,m,ans,cnt,tot;
inline void read(int& qwq){
	int awa = 0,w = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9'){awa = awa * 10 + ch - '0';ch = getchar();}
	qwq = awa * w;
}
bool vis[maxn];
int to[maxn*2],vlu[maxn*2],nxt[maxn*2],head[maxn];
priority_queue<pair<int,int> > p;
inline void insert(int u,int v,int w){
	to[++tot] = v;
	vlu[tot] = w;
	nxt[tot] = head[u];
	head[u] = tot;
}
void prim(int root){
	p.push(make_pair(0,root));
//	cnt++;
	while(!p.empty()){
		int u=p.top().second,res=p.top().first;
		p.pop();
		if(vis[u]) continue;
		res *= -1,ans += res;
		cnt++;
		vis[u] = 1;
		for(int i=head[u];i;i=nxt[i]){
			int v=to[i],w=vlu[i];
			if(vis[v]) continue;
			p.push(make_pair(-w,v));
//			cnt++;//cnt一定要在成功插入一个点时再统计吗? 
		}
	}
}
int main() {
	read(n),read(m);
	int u,v,w;
	for(int i=1; i<=m; i++) {//有向图不能使用prim 无向图需建双重边 
		read(u),read(v),read(w);
		insert(u,v,w);
		insert(v,u,w);
	}
	prim(1);//O((m+n)logn) 稠密图中常用	
//	cout<<cnt<<endl;
	if(cnt == n) cout<<ans;//注意有解条件 prim插入的是点 
	else cout<<"orz";
	return 0;
}
2024/10/23 22:00
加载中...