首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >洛谷P2792 [JSOI2008]小店购物(最小树形图)

洛谷P2792 [JSOI2008]小店购物(最小树形图)

作者头像
attack
发布2018-12-19 16:44:23
3400
发布2018-12-19 16:44:23
举报

题意

题目链接

Sol

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

然后发现死活都过不去

看了题解才发现题目中有个细节——买了\(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;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-11-28 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题意
  • Sol
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档