在写这道题之前，你要学会一个前置知识：

最小树形图

如果你没学过这个前置知识，建议你先看看这篇学习笔记。

现在默认你学会了最小树形图。

读完题很容易想到大体思路为根据这 $k$ 个情报建立有向边，然后在建好的图上跑一边最小树形图，这个题就做完了。

接下来考虑一些实现的细节：

1. 总有一些国家按“原价”攻打（即不出现在情报的末点位置），我们不妨建立一个超级根节点，让这个点向所有无入边的节点建立有向边，以超级根节点为 $root$ 跑一遍。

2. 考虑这个情况：有两个国家互相指向对方，那么先把其中一个全打下再去打另一个显然是不优的，应该先摸一下其中某个国家，这样两个国家都有“优惠”。具体地，每个节点本来表示每个国家要被攻打 $t_i$ 次，将其拆成两个节点，表示这个国家被攻打 $1$ 次和攻打 $t_i-1$ 次。

然后上 code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int re(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
const int N=1e4+10;
struct node{
	int u,v;
	double w;
}a[N];
int fa[N];
int ffa[N];
int cc[N],vis[N];
int n,m,root;
int tot;
double ans,mn[N],s[N];
int id[N][2];
int t[N];
int k;
int idx;
inline void inits(){
	for(int i=1;i<=n;i++)mn[i]=0x3f3f3f3f3f3f3f3f;
	memset(fa,0,sizeof fa);
	memset(vis,0,sizeof vis);
	memset(ffa,0,sizeof ffa);
	memset(cc,0,sizeof cc);
	tot=0;
}
inline void zhuliu(){
	while(1){
		inits();
		for(int i=1;i<=m;i++){
			if(a[i].u!=a[i].v&&a[i].w<mn[a[i].v]){
				mn[a[i].v]=a[i].w;
				fa[a[i].v]=a[i].u;
			}
		}
		for(int i=1;i<=n;i++)if(i!=root&&!fa[i]){
			ans=-1;
			return;
		}
		mn[root]=0;
		for(int i=1;i<=n;i++){
			ans+=mn[i];
			int now=i;
			while(now!=root&&vis[now]!=i)vis[now]=i,now=fa[now];
			if(now!=root&&!cc[now]){ 
				cc[now]=++tot;
				while(now!=root&&!cc[fa[now]]){
					now=fa[now];
					cc[now]=tot;
				}
			}
		}
		if(!tot)return;
		for(int i=1;i<=n;i++)if(!cc[i])cc[i]=++tot;
		for(int i=1;i<=m;i++){
			if(a[i].u!=a[i].v)a[i].w-=mn[a[i].v];
			a[i].u=cc[a[i].u];
			a[i].v=cc[a[i].v];
		}
		n=tot,root=cc[root];
	}
}
signed main(){
	n=re();
	root=++idx;
	for(int i=1;i<=n;i++){
		cin>>s[i]>>t[i];
		if(t[i]>0)id[i][0]=++idx,a[++m]=(node){root,id[i][0],s[i]};
		if(t[i]>1)id[i][1]=++idx,a[++m]=(node){root,id[i][1],s[i]*(t[i]-1)};
	}
	k=re();
	for(int i=1;i<=k;i++){
		int u=re(),v=re();
		double w;cin>>w;
		if(t[u]>0&&t[v]>0)a[++m]=(node){id[u][0],id[v][0],w};
		if(t[u]>0&&t[v]>1)a[++m]=(node){id[u][0],id[v][1],w*(t[v]-1)};
		if(t[u]>1&&t[v]>0)a[++m]=(node){id[u][1],id[v][0],w};
		if(t[u]>1&&t[v]>1)a[++m]=(node){id[u][1],id[v][1],w*(t[v]-1)};
	}
	n=idx;
	zhuliu();
	cout<<fixed<<setprecision(2)<<ans;
	return 0;
}

一些非常致命的注意事项（这导致我调了很久很久，真的很久很久）：

1. 能不能建边取决于攻击次数和 $0$ 的大小关系，能不能拆点取决于攻击次数和 $1$ 的大小关系。

2. 点的编号一定要从 $1$ 开始且连续，拆点我本来写的 $i$ 和 $i+n$ ，但如果中间有一些点的攻击次数为 $0$ 这样点编号不连续调那个 $zhuliu$ 函数相当麻烦。所以每次加新点就用了 $idx$ ，而且一定要记得跑 $zhuliu$ 之前令 n=idx 。

3. 输出答案保留两位小数。

4. double类型的数组（ $mn[]$ ）赋极大值不能用memset，自己手动 0x 八个 3f。

5. 找环的过程放进了统计答案里面，因为根据题意建出来的图不一定联通。而且环处理的时候一定要谨慎一点，想明白了再写。

完结撒花✿✿ヽ(°▽°)ノ✿！