题解

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 105
#define maxm 5105
using namespace std;
int n,m,a,b,tim[maxn],sum[maxn],flag[maxn];
double c,ans;
int tmp,best[maxn],bel[maxn],idx,vis[maxn];
struct Graph{
    int tot,now[maxn],fa[maxm],son[maxm],pre[maxm];
    double val[maxm];
    void init(){tot=0;memset(now,0,sizeof(now));}
    void put(int a,int b,double c){pre[++tot]=now[a],now[a]=tot,son[tot]=b,val[tot]=c,fa[tot]=a;}
    void prepare(){
        for (int u=0;u<=n;u++) if (!flag[u])
            for (int p=now[u],v=son[p];p;p=pre[p],v=son[p])
                if (best[v]==-1||val[best[v]]>val[p]) best[v]=p;
        memset(vis,-1,sizeof(vis));
        tmp=n,vis[0]=0;
        for (int i=1;i<=n;i++) if (!flag[i]&&vis[i]==-1){
            int u,v; ++idx;
            for (u=i;vis[u]==-1;u=fa[best[u]]) vis[u]=idx;
            if (vis[u]<idx) continue;
            v=u,bel[u]=++tmp,vis[v]=0;
            for (v=fa[best[v]];vis[v]==idx;v=fa[best[v]]) vis[v]=0,bel[v]=tmp;
        }
    }
}G[2];
void work(){
    for (int t=1;;t^=1){
        for (int i=0;i<=n;i++) best[i]=-1;
        G[t].prepare(),G[t^1].init();
        if (tmp==n){
            for (int i=1;i<=n;i++) if (!flag[i]) ans+=G[t].val[best[i]];
            break;
        }
        for (int u=0;u<=n;u++) if (!flag[u]){
            for (int p=G[t].now[u],v=G[t].son[p];p;p=G[t].pre[p],v=G[t].son[p]){
                if (bel[u]&&bel[v]&&bel[u]==bel[v]) continue;
                int a;
                if (bel[u]) a=bel[u]; else a=u;
                if (bel[v]) G[t^1].put(a,bel[v],G[t].val[p]-G[t].val[best[v]]);
                else G[t^1].put(a,v,G[t].val[p]);
            }
            if (bel[u]) ans+=G[t].val[best[u]],flag[u]=1;
        }
        n=tmp;
    }
    printf("%.2lf\n",ans);
}
double low[maxn];
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%lf%d",&c,&tim[i]);
        if (tim[i]) G[1].put(0,i,c),low[i]=c; else flag[i]=1;
    }
    scanf("%d",&m);
    for (int i=1;i<=m;i++){
        scanf("%d%d%lf",&a,&b,&c);
        if (flag[a]||flag[b]) continue;
        low[b]=min(low[b],c);
        G[1].put(a,b,c);
    }
    for (int i=1;i<=n;i++) if (!flag[i]) ans+=low[i]*(tim[i]-1);
    work();
    return 0;
}