题意
Sol
一开始的思路：新建一个虚点向每个点连边，再加上题面中给出的边，边权均为大小*需要购买的数量
然后发现死活都过不去
看了题解才发现题目中有个细节——买了\(A\)就可以买\(B\)，但是人家没告诉你必须买够\(A\)的数量才能买\(B\)呀qwqqqqqqq
所以建图的时候只算一次贡献就行了
这样剩下的个数都可以通过最小值买到
// luogu-judger-enable-o2#includeusing namespace std;const int MAXN = 1e5 + 10, INF = 1e9 + 10;inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c -'0', c = getchar(); return x * f;}int N, M, R, m[MAXN], id[MAXN], vis[MAXN], fa[MAXN];double mn[MAXN], val[MAXN];struct Edge { int u, v; double w; int nxt;}E[MAXN];int head[MAXN], num = 1;inline void AddEdge(int x, int y, double w) { E[num] = (Edge) {x, y, w, head[x]}; head[x] = num++;}double ZhuLiu() { double ans = 0; R = N; while("Liang Liang") { for(int i = 1; i <= N; i++) id[i] = vis[i] = 0, mn[i] = 1e9; int cnt = 0, x; for(int i = 1; i <= num; i++) if(E[i].v != E[i].u && (mn[E[i].v] > E[i].w)) mn[E[i].v] = E[i].w, fa[E[i].v] = E[i].u; mn[R] = 0; for(int i = 1; i <= N; i++) { ans += mn[i]; for(x = i; (!id[x]) && (vis[x] != i) && x != R; x = fa[x]) vis[x] = i; //tag if(x != R && (!id[x])) { id[x] = ++cnt; for(int t = fa[x]; t != x; t = fa[t]) id[t] = cnt; } } if(cnt == 0) return ans; for(int i = 1; i <= N; i++) if(!id[i]) id[i] = ++cnt; for(int i = 1; i <= num; i++) { double pre = mn[E[i].v]; if((E[i].u = id[E[i].u]) != (E[i].v = id[E[i].v])) E[i].w -= pre; } N = cnt; R = id[R]; } return ans;}int main() { N = read(); for(int i = 1; i <= N; i++) { scanf("%lf", &val[i]), m[i] = read(), AddEdge(N + 1, i, val[i]); } N++; M = read(); for(int i = 1; i <= M; i++) { int x = read(), y = read(); double z; scanf("%lf", &z); AddEdge(x, y, z); val[y] = min(val[y], z); } double ans = 0; for(int i = 1; i <= N - 1; i++) ans += 1.0 * (m[i] - 1) * val[i];// printf("%d\n", m[i] - 1); printf("%.2lf", ans + ZhuLiu()); return 0;}