不会最小树形图的出门左转
其实如果确定每种商品第一件的购买顺序，那么剩下的商品肯定是以最优惠价格购买的。
如何确定各种商品第一件购买时的最小价值呢？
考虑如果购买了(a_i)这种商品，那么就能以(c_i)的价格购买(b_i)这种商品，考虑从(a_i)往(b_i)连权值为(c_i)的有向边。
初始建一个额外的(S)点往所有点i连权值为(v_i)的有向边。
然后用朱刘算法求一遍最小树形图就行了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long long
const double INF=1e9;
const int N=110;
const int M=10100;
int n,m,r,tru[N];
double ans,mn[N],c[N],num[N];
struct edge{
int u,v;
double w;
}e[M];
int cnt,id[N],top[N],fa[N];
bool work(){
while(2333){
memset(id,0,sizeof(id));
memset(top,0,sizeof(top));
for(int i=1;i<=n;i++)mn[i]=INF;
for(int i=1;i<=m;i++)
if(e[i].u!=e[i].v&&e[i].w<mn[e[i].v])
fa[e[i].v]=e[i].u,mn[e[i].v]=e[i].w;
mn[r]=0;fa[r]=0;
for(int i=1;i<=n;i++)if(mn[i]==INF)return false;
int u;
for(int i=1;i<=n;i++){
ans+=mn[i];
for(u=i;u!=r&&top[u]!=i&&!id[u];u=fa[u])top[u]=i;
if(u!=r&&!id[u]){
id[u]=++cnt;
for(int v=fa[u];v!=u;v=fa[v])id[v]=cnt;
}
}
if(!cnt)return true;
for(int i=1;i<=n;i++)if(!id[i])id[i]=++cnt;
for(int i=1;i<=m;i++){
double last=mn[e[i].v];
e[i].u=id[e[i].u];e[i].v=id[e[i].v];
if(e[i].u!=e[i].v)e[i].w-=last;
}
n=cnt;
r=id[r];
cnt=0;
}
}
int read(){
int sum=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
return sum*f;
}
signed main(){
int tot=read();n=0;
for(int i=1;i<=tot;i++){
scanf("%lf",&c[++n]);
num[n]=read()-1;
if(num[n]<0){n--;continue;}
tru[i]=n;
}
m=read();
r=++n;
for(int i=1;i<=n-1;i++)e[m+i].u=r,e[m+i].v=i,e[m+i].w=c[i];
for(int i=1;i<=m;i++){
int u=read(),v=read();
double w;
scanf("%lf",&w);
if(tru[v]==0||tru[u]==0)continue;
e[i].u=tru[u];e[i].v=tru[v];e[i].w=w;
c[tru[v]]=min(c[tru[v]],w);
}
m+=n-1;
for(int i=1;i<=n-1;i++)ans+=num[i]*c[i];
if(work())printf("%.2lf",ans);
else printf("-1");
return 0;
}