管道储液系统

测评请前往##Luogu##

题目背景

A市有一个管道储液系统，每次可以用来存储很多A市生产出的一些有特殊性质的液体。

题目描述

管道系统一共有 $M$ 条海拔水平一致的管道，每个管道都有一个容积 $V_i$ ，管道由 $N$ 个控制阀门(编号为 $1$ 至 $N$ )相互连接。

由于一些原因，要使这些控制阀门在用管道互相连接后形成一棵或多棵树的结构。为了防止内部溶液流出，每条管道一定在两端各连接着控制阀门。

对于每条管道，都有一个允许的内部液体的相对压强范围 $[B_i,E_i] (B_i \ge 0,E_i \ge 0)$ 表示该管道对可以装入的液体的要求。相对压强最小为0。

由于这些液体的特殊性质，你可以加固一些管道，加固后的管道在可容纳的液体相对压强范围会变为 $[B_i - K, E_i + K]$ 。但是它的容积会比原来减少 $W$ 。管道的容积减少为0的时候将不再连通。加固的操作可以重复多次。

在加入液体时从 $1$ 号控制阀门加入且控制阀门不会允许一个管道流入不符合压强的范围的液体。

输入输出格式

输入格式

第一行 $5$ 个整数 $N,M,K,W,D$ ，其中 $N,M,K,W$ 表示描述中的值， $D$ 表示液体种类数量。

第 $2$ 行到第 $M + 1$ 行，每行 $5$ 个整数 $P_i,Q_i,V_i,B_i,E_i$ ，分别表示该管道连接的两个控制阀门，该管道的容积和该管道允许的相对压强范围 $[B_i,E_i]$ (保证 $B_i \le E_i$ )。

第 $M + 2$ 行到第 $M + D + 1$ 行每行一个整数 $R$ ，表示每种液体可能产生的最大压强。

输出格式

共 $D$ 行，表示每种液体装在该管道系统中的最大容积。

输入输出样例

输入样例#1:

输出样例#1:

输入样例#2:

输出样例#2:

17
19
19

输入样例#3:

输出样例#3:

12
11

输入样例#4:

10 19 4 6 5
1 3 2 1 4
1 3 4 2 3
1 5 60 7 8
3 10 7 10 13
3 5 20 40 41
3 6 16 1 2
10 9 8 9 11
8 10 6 1 11
6 9 40 7 13
6 8 2 1 1
8 9 4 5 6
2 8 40 33 55
6 7 5 4 5
7 8 7 20 21
5 7 1 1 1
5 7 4 2 3
2 7 5 1 3
4 5 4 2 100
2 4 100 1 1
1
2
33
43
50

输出样例#4:

说明

数据说明

对于前20%的数据，保证 $D = 1, R_1 = 7, R_2 = 13, N \le 100, M \le 1000, B_i = E_i, K = 0,W = 0$
对于前40%的数据，保证 $D = 1, N \le 100, M \le 1000, B_i = E_i, K = 0,W = 0$
对于前60%的数据，保证 $D \le 10, K = 0, W = 0, N \le 500, M \le 10000$
对于前100%的数据，保证 $D \le 10, N \le 5000, M \le 200000, V_i \le 10^9$

标程

标程#1 - CHY

#include <bits/stdc++.h>
using namespace std;

//切记!数据范围过大开long long!

int n_node, n_side, v_change, n_liquid, cost;
long long max_count = 1, max_volume = 0;
long long now_pressure = 0;

struct Pipe
{
    int node_;
    int _node;
    long long volume;
    int pressure_max;
    int pressure_min;
    bool operator<(const Pipe p)
    //优先队列重载运算符
        const
    {
        return this->volume < p.volume;
    }
};

priority_queue<Pipe> const_pipes;
//最初的优先队列
priority_queue<Pipe> temp_pipes;
//对于每一个密度独立的优先队列
vector<int> father;
//并查集father
vector<int> node_num;
//节点数目
vector<long long> tot_volume;
//最大容积

inline long long max(long long a,long long b)
//没有long long的max()?自己写一个
{
    return a > b ? a : b;
}

void getdata()
//获取数据
{
    cin >> n_node >> n_side >> v_change >> cost >> n_liquid;
    for (int i = 0; i < n_side; i++)
    {
        Pipe p;
        cin >> p._node >> p.node_ >> p.volume >> p.pressure_min >> p.pressure_max;
        const_pipes.push(p);
    }
    return;
}

void init()
//初始化
{
    temp_pipes = const_pipes;
    //获取原始队列
    father.clear();
    for (int i = 0; i <= n_node + 1; i++)
        father.push_back(i);
    //清空初始化father
    vector<int> t(n_node + 1, 1);
    node_num = t;
    //初始化数量
    max_count = 1;
    //最大数量
    vector<long long> q(n_node + 1, 0);
    tot_volume = q;
    //初始化总容积
    max_volume = 0;
    //最大容积
    now_pressure = 0;
    //当前压力
    return;
}

//并查集套路
int find(int x)
{
    return father[x] == x ? x : father[x] = find(father[x]);
}

void merge(int a, int b)
{
    a = find(a);
    b = find(b);
    if (a == b)
        return;
    father[a] = b;
    node_num[b] += node_num[a];
    max_count = max(node_num[b], max_count);
    return;
}

void addVolume(Pipe p)
//增加容积(核心)
//容积记录在并查集父节点的对应数组位置
{
    long long cur_volume = tot_volume[find(p.node_)] + tot_volume[find(p._node)] + p.volume;
    //当前集合的容积 = 两边的集合的总容积 + 当前边的容积
    merge(p.node_, p._node);
    //得出总容积之后合并
    if (find(p.node_) == find(1))
        max_volume = max(max_volume, cur_volume);
    //如果和1号点连通就让最大容积更新
    tot_volume[find(p.node_)] = cur_volume;
    //当前集合的容积更新
}

void updataPipe()
//重载管道属性
{
    priority_queue<Pipe> tmp;

    if (v_change <= 0 || cost <= 0)
    //如果管道不可以加固
    {
        while (!temp_pipes.empty())
        {
            //依次取出判断是否可以容纳后再次入队
            Pipe p = temp_pipes.top();
            temp_pipes.pop();
            if (p.volume > 0 && p.pressure_max >= now_pressure && p.pressure_min <= now_pressure)
                tmp.push(p);
        }
    }
    else
    {
        while (!temp_pipes.empty())
        {
            //依次取出判断是否可以容纳后再次入队
            Pipe p = temp_pipes.top();
            temp_pipes.pop();
            if (p.pressure_max >= now_pressure && p.pressure_min <= now_pressure)
            //如果可以直接入队
            {
                tmp.push(p);
                continue;
            }
            while (p.volume > 0 && (p.pressure_max < now_pressure || p.pressure_min > now_pressure))
            //否则在容积 > 0 并且 在压力范围外 的时候进行循环
            //此处用公式法会WA点
            {
                p.volume -= cost;           //体积减少
                p.pressure_max += v_change; //范围扩大
                p.pressure_min -= v_change;
                if (p.pressure_min < 0)     //最小压力为0
                    p.pressure_min = 0;
            }
            if (p.volume > 0)   //如果不是因为容积过小而跳出那就是进入范围了
                tmp.push(p);    //入队
        }
    }
    temp_pipes = tmp;   //队列赋值
    return;
}

void work()
{
    while (!temp_pipes.empty() && max_count < n_node)
    //依次取出管道
    {
        Pipe p = temp_pipes.top();
        temp_pipes.pop();
        if (find(p.node_) != find(p._node)) //如果两端不在同一个集合内
            addVolume(p);                   //增加容积
    }
}

int main()
{
    ios::sync_with_stdio(false);    //快读
    getdata();                      //读数据
    while (n_liquid--)              //每种液体
    {
        init();
        cin >> now_pressure;        //读入压力
        updataPipe();               //更新管道信息
        work();                     //计算最大生成树
        cout << max_volume << endl;
    }
    return 0;
}