经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
洛谷P2792 [JSOI2008]小店购物(最小树形图)
来源:cnblogs  作者:自为风月马前卒  时间:2018/11/29 9:27:45  对本文有异议

题意

题目链接

Sol

一开始的思路:新建一个虚点向每个点连边,再加上题面中给出的边,边权均为大小*需要购买的数量

然后发现死活都过不去

看了题解才发现题目中有个细节——买了\(A\)就可以买\(B\),但是人家没告诉你必须买够\(A\)的数量才能买\(B\)呀qwqqqqqqq

所以建图的时候只算一次贡献就行了

这样剩下的个数都可以通过最小值买到

  1. // luogu-judger-enable-o2
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. const int MAXN = 1e5 + 10, INF = 1e9 + 10;
  5. inline int read() {
  6. char c = getchar(); int x = 0, f = 1;
  7. while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
  8. while(c >= '0' && c <= '9') x = x * 10 + c -'0', c = getchar();
  9. return x * f;
  10. }
  11. int N, M, R, m[MAXN], id[MAXN], vis[MAXN], fa[MAXN];
  12. double mn[MAXN], val[MAXN];
  13. struct Edge {
  14. int u, v; double w; int nxt;
  15. }E[MAXN];
  16. int head[MAXN], num = 1;
  17. inline void AddEdge(int x, int y, double w) {
  18. E[num] = (Edge) {x, y, w, head[x]}; head[x] = num++;
  19. }
  20. double ZhuLiu() {
  21. double ans = 0; R = N;
  22. while("Liang Liang") {
  23. for(int i = 1; i <= N; i++) id[i] = vis[i] = 0, mn[i] = 1e9; int cnt = 0, x;
  24. for(int i = 1; i <= num; i++)
  25. if(E[i].v != E[i].u && (mn[E[i].v] > E[i].w))
  26. mn[E[i].v] = E[i].w, fa[E[i].v] = E[i].u;
  27. mn[R] = 0;
  28. for(int i = 1; i <= N; i++) {
  29. ans += mn[i];
  30. for(x = i; (!id[x]) && (vis[x] != i) && x != R; x = fa[x]) vis[x] = i; //tag
  31. if(x != R && (!id[x])) {
  32. id[x] = ++cnt;
  33. for(int t = fa[x]; t != x; t = fa[t]) id[t] = cnt;
  34. }
  35. }
  36. if(cnt == 0) return ans;
  37. for(int i = 1; i <= N; i++) if(!id[i]) id[i] = ++cnt;
  38. for(int i = 1; i <= num; i++) {
  39. double pre = mn[E[i].v];
  40. if((E[i].u = id[E[i].u]) != (E[i].v = id[E[i].v])) E[i].w -= pre;
  41. }
  42. N = cnt; R = id[R];
  43. }
  44. return ans;
  45. }
  46. int main() {
  47. N = read();
  48. for(int i = 1; i <= N; i++) {
  49. scanf("%lf", &val[i]), m[i] = read(), AddEdge(N + 1, i, val[i]);
  50. }
  51. N++;
  52. M = read();
  53. for(int i = 1; i <= M; i++) {
  54. int x = read(), y = read(); double z; scanf("%lf", &z);
  55. AddEdge(x, y, z); val[y] = min(val[y], z);
  56. }
  57. double ans = 0;
  58. for(int i = 1; i <= N - 1; i++) ans += 1.0 * (m[i] - 1) * val[i];// printf("%d\n", m[i] - 1);
  59. printf("%.2lf", ans + ZhuLiu());
  60. return 0;
  61. }
 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号