题意分析

题目背景

本题属于流体模拟与优先队列应用问题，描述水在管道系统中的流动过程。关键点在于计算水从注入点到目标水位所需时间，考虑连接管对水流分配的影响。

核心问题

1. 管道系统建模：
   • 垂直管道：直径1cm，由坐标$(x,y)$和高度定义。
   • 连接管：水平细管，连接两根垂直管道，忽略其水量。
2. 水流规则：
   • 水从第一根管道顶部注入，速度$0.25\pi \text{cm}^3/\text{s}$。
   • 水位达到连接管时，水流入相连管道，后续填充速度减半。
3. 目标：计算水到达目标管道指定水位的时间，或判断不可达。

输入输出

• 输入：
  • 测试用例数$t$。
  • 每个测试用例包含：
    • 管道数量$p$及每根管道的坐标和高度。
    • 连接管数量$l$及每条连接管的坐标和长度。
    • 目标管道编号和水位$y$坐标。
• 输出：到达时间（秒）或No Solution。

解题思路

1. 数据结构设计

• 管道信息：存储每根管道的顶部坐标$(x,y)$、底部$y$坐标（$y + \text{高度}$）和当前水位。
• 连接关系：使用邻接表e[]记录每根管道在各水位处的连接情况（目标管道或特殊标记）。

2. 水位更新策略

1. 优先队列：按水位从高到低处理，确保每次处理当前最高水位。
2. 事件处理：
   • 水位达到连接管时，将相连管道加入队列。
   • 水位达到目标时标记成功。
   • 水位低于目标且无更多连接时终止。

3. 水量计算

• 累加水量：每次水位变化时，计算水量增量$\Delta V = \pi \cdot r^2 \cdot \Delta h = 0.25\pi \cdot \Delta h$。
• 时间转换：总时间$T = \frac{\text{总水量}}{0.25\pi}$。

4. 关键算法

• 反向处理：从底部向上填充，优先处理高水位。
• 速度调整：当多根管道同时填充时，实际速度为$\frac{0.25\pi}{k}$（$k$为活跃管道数）。

算法实现

代码框架

```cpp
#include <bits/stdc++.h>
using namespace std;
#define maxp 30

int cases, pipes, l, target, level, tot_water;
int w, p, pp;
int px[maxp], py[maxp], bottom[maxp], water[maxp];
bool find_ans;
set<int> links; // 将变量名从 link 改为 links
list<pair<int, int> > e[maxp];
priority_queue<pair<int, int> > pq;

void read() {
    cin >> pipes;
    for (int i = 0; i < pipes; i++) {
        int tmp;
        cin >> px[i] >> py[i] >> tmp;
        bottom[i] = py[i] + tmp;
        water[i] = -1;
        e[i].clear();
    }
    cin >> l;
    links.clear(); // 使用新的变量名 links
    for (int i = 0; i < l; i++) {
        int lx, ly, len, lk1 = -1, lk2 = -1;
        cin >> lx >> ly >> len;
        for (int j = 0; j < pipes; j++) {
            if (bottom[j] >= ly && py[j] <= ly) {
                if (px[j] + 1 == lx) lk1 = j;
                if (px[j] == lx + len) lk2 = j;
                if (lk1 != -1 && lk2 != -1) break;
            }
        }
        links.insert(ly);
        e[lk1].push_back(make_pair(ly, lk2));
        e[lk2].push_back(make_pair(ly, lk1));
    }
    cin >> target >> level;
    links.insert(level);
    target--;
}

bool init() {
    if (level < py[target]) {
        cout << "No Solution\n";
        return false;
    }
    if (py[target] <= level && level <= bottom[target]) {
        e[target].push_back(make_pair(level, -2));
    }
    for (int i = 0; i < pipes; i++) {
        for (set<int>::const_iterator j = links.lower_bound(py[i]); j != links.end() && *j < bottom[i]; j++) {
            e[i].push_back(make_pair(*j, i));
        }
        e[i].push_back(make_pair(py[i], -1));
        e[i].sort();
        e[i].reverse();
    }
    return true;
}

void solve() {
    while (!pq.empty()) pq.pop();
    water[0] = bottom[0];
    pq.push(make_pair(water[0], 0));
    find_ans = false;
    tot_water = 0;
    while (!pq.empty()) {
        w = pq.top().first;
        p = pq.top().second;
        pq.pop();
        if (p == -1) break;
        else if (p == -2) {
            find_ans = true;
            break;
        }
        tot_water += (water[p] - w);
        water[p] = w;
        while (!e[p].empty() && e[p].front().first == water[p]) {
            pp = e[p].front().second;
            if (pp < 0) pq.push(e[p].front());
            else if (water[pp] == -1) {
                water[pp] = bottom[pp];
                pq.push(make_pair(water[pp], pp));
            }
            e[p].pop_front();
        }
        if (!e[p].empty()) pq.push(make_pair(e[p].front().first, p));
    }
}

int main() {
    cin >> cases;
    while (cases--) {
        read();
        if (!init()) continue;
        solve();
        if (find_ans)
            cout << tot_water << '\n';
        else
            cout << "No Solution\n";
    }
    return 0;
}

#### **关键步骤**
1. **输入处理**：读取管道和连接管数据，构建邻接表。
2. **初始化**：从第一根管道底部开始注水。
3. **模拟循环**：
   - 处理最高水位管道。
   - 累加水量，更新连接管道水位。
   - 检查是否到达目标。
4. **结果输出**：根据总水量计算时间或输出无解。

---

### **复杂度分析**
- **时间**：$O(t \cdot (p + l \log l))$，其中优先队列操作为$O(\log l)$。
- **空间**：$O(p + l)$，存储管道和连接关系。