爆零求调

#include<bits/stdc++.h>
using namespace std;
int n,k,f[51];
double cnt=0;
bool vis[51]={0};
struct ddd{
	double c;
	int m;
}a[51];
struct dd{
	int A,B;
	double P;
}b[501];
int check(int l){
	if(f[l]==l)return l;
	return f[l]=check(f[l]);
}
bool cmp(dd l,dd p){
	return l.P*(a[l.B].c-a[l.B].m)>p.P*(a[p.B].c-a[p.B].m);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].c>>a[i].m;
	cin>>k;
	for(int i=0;i<k;i++)cin>>b[i].A>>b[i].B>>b[i].P;
	sort(b,b+k,cmp);
	for(int i=1;i<=k;i++)f[i]=i;
	for(int i=0;i<k;i++){
		int u=check(b[i].A),v=check(b[i].B);
		if(u==v)continue;
		f[u]=v;
		cnt+=(a[b[i].B].m*b[i].P);
		vis[b[i].B]=1;
	}
	for(int i=1;i<=n;i++)if(vis[i]==0)cnt+=(a[i].c*a[i].m);
	printf("%.2f",cnt);
	return 0;
}