有大佬帮我看看为什么我的代码RE,找不到原因
  • 板块P2700 逐个击破
  • 楼主AI_AC
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/10/10 17:15
  • 上次更新2023/11/2 14:39:11
查看原帖
有大佬帮我看看为什么我的代码RE,找不到原因
780913
AI_AC楼主2023/10/10 17:15
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<sstream>
#include<cmath>
#include<list>
#include<bitset>
#include<unordered_map>
#include<unordered_set>

#define bitcnt(x) (__builtin_popcountll(x))//ll二进制数中1的个数
#define endl '\n'
#define lson pos<<1
#define rson pos<<1|1

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using namespace std;
const int N=5000010;
struct edge{
	int u,v,w;
}e[N];
int idx=0;
int n,k;
int fa[N];
bool vis[N];
bool cmp(const edge& a,const edge& b){
	a.w>b.w;
}
void init(int n){
	for(int i=0;i<=n;i++) fa[i]=i;
}
int find(int x){
	while(x!=fa[x]) x=fa[x]=fa[fa[x]];
	return x;
}
void solve(){
	cin>>n>>k;
	ll res=0;
	int x;
	init(n);
	for(int i=1;i<=k;i++) cin>>x,vis[x]=1; 
	for(int i=1;i<=n-1;i++){
		int a,b,c;
		cin>>a>>b>>c;
		e[++idx]={a,b,c};
		res+=c;
	}
	// cout<<res<<endl;
	sort(e+1,e+idx+1,cmp);
	for(int i=1;i<=idx;i++){
		int fx=find(e[i].u);
		int fy=find(e[i].v);
		if(vis[fx]==1&&vis[fy]==1) continue;
		res-=e[i].w;
		fa[fx]=fy;
		if(vis[fx]) vis[fy]=1;
	}
	cout<<res<<endl;
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int t=1;
	//cin>>t;
	while(t--){
		solve();
	}

	return 0;
}
2023/10/10 17:15
加载中...