Submission #3473138

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, P> Pll;
int par[200002];
int rk[200002];
 
void init(int n){
	for(int i=0; i<n; i++){
		par[i]=i;
		rk[i]=0;
	}
}
 
int find(int x){
	if(par[x]==x){
		return x;
	}else{
		return par[x]=find(par[x]);
	}
}
 
void unite(int x, int y){
	x=find(x);
	y=find(y);
	if(x==y) return;
	if(rk[x]<rk[y]){
		par[x]=y;
	}else{
		par[y]=x;
		if(rk[x]==rk[y]) rk[x]++;
	}
}
 
bool same(int x, int y){
	return find(x)==find(y);
}

int main()
{
	int n, m, k;
	cin>>n>>m>>k;
	init(n+k);
	int c[100000];
	int ct[100000]={};
	for(int i=0; i<n; i++){
		cin>>c[i];
		if(c[i]){
			unite(i, n+c[i]-1);
			ct[c[i]-1]++;
		}
	}
	int ct0=0;
	for(int i=0; i<k; i++){
		if(ct[i]>0) ct0+=(ct[i]-1);
	}
	Pll e[100000];
	for(int i=0; i<m; i++){
		int a, b; ll w;
		cin>>a>>b>>w;
		a--; b--;
		unite(a, b);
		e[i]=Pll(w, P(a, b));
	}
	vector<int> vr[100000];
	int r[100000];
	for(int i=0; i<n; i++){
		r[i]=find(i);
		vr[r[i]].push_back(i);
	}
	int rn=0;
	for(int i=0; i<n; i++){
		if(!vr[i].empty()) rn++;
	}
	init(n+k);
	for(int i=0; i<n; i++){
		cin>>c[i];
		if(c[i]) unite(i, n+c[i]-1);
	}
	int ct1=n-k-ct0;
	if(ct1-(rn-1)<0){
		cout<<-1<<endl;
		return 0;
	}
	sort(e, e+m);
	ll ans=0;
	vector<ll> use;
	for(int i=0; i<m; i++){
		if(!same(e[i].second.first, e[i].second.second)){
			unite(e[i].second.first, e[i].second.second);
			use.push_back(e[i].first);
		}
	}
	int c0=ct1-rn+1;
	while(!use.empty()){
		if(c0==0) break;
		use.pop_back();
		c0--;
	}
	for(int i=0; i<use.size(); i++) ans+=use[i];
	cout<<ans<<endl;
    return 0;
}

Submission Info

Judge Result