蓝桥杯-城市建设

读完题就知道是生成树的题，然后注意一下就是，找完一颗树之后，遍历剩下的边，小于0就在加上即可。先找没河的，再加上有河的再跑一遍克鲁斯卡尔就好了。

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
int n,m;

const int N=1e4+34;
int f[N];
LL res,ans;
struct uzi
{
	int s,t,w;
	uzi(){}
	uzi(int A,int B,int C){s=A;t=B;w=C;}
	bool operator < (const uzi &t)const{
		return w<t.w;
	}
};
vector<uzi>v;
int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
int main(){
	// freopen("in.txt","r",stdin);
	 ios::sync_with_stdio(false);
	cin>>n>>m;
	res=1e18;
	for(int i=1;i<=n+1;i++)f[i]=i;
	for(int i=1;i<=m;i++){
		int s,t,w;
		cin>>s>>t>>w;
		v.pb(uzi(s,t,w));
	}
	int cnt=0,pos=m;
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++){
		uzi k=v[i];
		int x=find(k.s),y=find(k.t);
		if(x==y&&k.w>=0)continue;
		else if(x==y){ans+=k.w;continue;}
		f[y]=x;
		ans+=k.w;
		if(++cnt==n-1){pos=i;break;}
		
	}	
	for(int i=pos+1;i<v.size();i++){
		if(v[i].w<0)ans+=v[i].w;
		else break;
	}
	if(cnt>=n-1)res=ans;
	// cout<<res<<endl;
	pos=m+n;
	for(int i=1;i<=n;i++){
		int f;
		cin>>f;
		if(f==-1)continue;
		v.pb(uzi(n+1,i,f));
	}
	cnt=ans=0;
	for(int i=1;i<=n+1;i++)f[i]=i;
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++){
		uzi k=v[i];
		int x=find(k.s),y=find(k.t);
		if(x==y&&k.w>=0)continue;
		else if(x==y){ans+=k.w;continue;}
		f[y]=x;
		ans+=k.w;
		if(++cnt==n){pos=i;break;}
	}
	for(int i=pos+1;i<v.size();i++){
		if(v[i].w<0)ans+=v[i].w;
		else break;
	}
	if(cnt>=n)res=min(res,ans);
	cout<<res<<endl;
	return 0;
}