TLE on #2求条
查看原帖
TLE on #2求条
465055
1004779564bzbjj楼主2024/8/5 10:36

有可能是:

1.常数太大(求优化)

2.有死循环之类的错误(球改)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,h[114514],d[114514],v[114514],bj[114514],tnt,hd[114514],ans;
struct node{
	ll x,y,z;
};
node a[2045141],b[2045141];
ll bp;
bool pcmp(node x,node y){
	return x.x<y.x;
}
bool cmp(node x,node y){
	if(h[x.y]!=h[y.y]){
		return h[x.y]>h[y.y];
	}
	else{
		return x.z<y.z;
	}
}
void dfs(int x){
	v[x]=1;
	tnt++;
	for(ll i=bj[x];i<=m;i++){
		if(a[i].x!=x)break;
		if(!v[a[i].y]){
			dfs(a[i].y);
		}
		
	}
}
ll fd(ll x){
	if(hd[x]==x)return x;
	else return fd(hd[x]);
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(ll i=1;i<=n;i++){
		cin>>h[i];
		d[i]=1;
	}
	for(ll i=1;i<=m;i++){
		cin>>a[i].x>>a[i].y>>a[i].z;
		if(h[a[i].x]<h[a[i].y]){
			swap(a[i].x,a[i].y);
		}
		if(h[a[i].x]==h[a[i].y]){
			m++;
			i++;
			a[i]=a[i-1];
			swap(a[i].x,a[i].y);
		}
	}
	sort(a+1,a+m+1,pcmp);
	for(ll i=1;i<=n;i++){
		bj[i]=0x3f3f3f3f;
	}
	for(ll j=m;j>=1;j--){
		if(j<bj[a[j].x])bj[a[j].x]=j;
	}
	dfs(1);
	cout<<tnt<<" ";
	for(ll i=1;i<=m;i++){
		if(v[a[i].x]&&v[a[i].y]){
			bp++;
			b[bp]=a[i];
		}
	}
	sort(b+1,b+bp+1,cmp);
	//cout<<endl;
	//for(int i=1;i<=5;i++){
	//	cout<<b[i].x<<" "<<b[i].y<<"  "<<b[i].z<<endl;
	//}
	for(ll i=1;i<=n;i++){
		hd[i]=i;
	}
	for(ll i=1;i<=bp;i++){
		if(fd(b[i].x)!=fd(b[i].y)){
			ans+=b[i].z;
			hd[fd(b[i].x)]=fd(b[i].y);
		}
	}
	cout<<ans;
	return 0;
}
/*
7 7
10 7 9 8 3 4 10
1 7 4
1 2 10
2 7 3
1 5 2
3 7 1
3 6 6
6 4 5

6 16
*/ 

2024/8/5 10:36
加载中...