三个点RE求解
查看原帖
三个点RE求解
382048
detor楼主2022/7/15 15:00
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
long long n,m,sum,hs;
int book[100010];
int tot,h[100010],v[200010],w[200010],ne[200010];
struct pir{
	int x,y;
}hp[200010];

void add(int a,int b,int c){
	v[tot]=b;w[tot]=c;ne[tot]=h[a];
	h[a]=tot++;
	return;
}
void siftdown(int i)
{
	if(i==0)return;
	int t=i;
	while(2*i<=hs)
	{
		if(hp[2*i].x<hp[t].x)
			t=2*i;
		if(2*i+1<=hs&&hp[2*i+1].x<hp[t].x)
			t=2*i+1;
		if(i!=t)
			swap(hp[i],hp[t]);
		else
			return;
		i=t;
	}
	return ;
}

void siftup(int i)
{
	while(i>1)
	{
		if(hp[i].x<hp[i/2].x)
			swap(hp[i],hp[i/2]);
		else
			return;
		i/=2;
	}
	
	return;
}
int main()
{
// 	freopen("kruskal.in","r",stdin);
	int a,b,c;
	cin>>n>>m;
	memset(h,-1,sizeof h);
	for(int i=0;i<m;i++){
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);
	}
	
	
	sum=0;
	hp[1].x=0;
	hp[1].y=1;
	hs++;
	while(hs)
	{

		pir t=hp[1];
		hp[1]=hp[hs--];
		siftdown(1);
		a=t.y;
		if(book[a]) 
			continue;
		book[a]=1;
		sum+=t.x;
		for(int i=h[a];~i;i=ne[i]){
			hs++;
			hp[hs].x=w[i],hp[hs].y=v[i];
			siftup(hs);
		}
			
	}
	
    for(int i=1;i<=n;i++){
        if(book[i]==0){
            cout<<"orz";
            return 0;
        }
    }
	cout<<sum<<endl;
	
	fclose(stdin);
	return 0;
}
2022/7/15 15:00
加载中...