一开始的思路：新建一个虚点向每个点连边，再加上题面中给出的边，边权均为大小*需要购买的数量
然后发现死活都过不去
看了题解才发现题目中有个细节——买了\(a\)就可以买\(b\)，但是人家没告诉你必须买够\(a\)的数量才能买\(b\)呀qwqqqqqqq
所以建图的时候只算一次贡献就行了
这样剩下的个数都可以通过最小值买到
我要评论// luogu-judger-enable-o2
#include<bits/stdc++.h>
using 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;
}
如对本文有疑问， 点击进行留言回复！！
一上来就问分布式事务了解吗？还好复习了这份神仙笔记，怼就完了
网友评论