2684. 「BalticOI 2013」管道 Pipes 题解

问题分析

我们有 $n$ 个水库，$m$ 条管道。对于每条管道 $(u,v)$：

• 如果从管道中间放水，流速为 $2d$，那么水库 $u$ 和 $v$ 各失水 $d$
• 如果往管道中间注水，流速为 $2p$，那么水库 $u$ 和 $v$ 各得水 $p$

设第 $i$ 条管道的流量变化为 $x_i$（正数表示注水，负数表示放水）。

1. 建立方程

对于水库 $i$，设与它相连的管道集合为 $E_i$，那么：

$$\sum_{j \in E_i} x_j = c_i$$

其中 $c_i$ 是水库 $i$ 的变化速度。

这是因为：每条与水库 $i$ 相连的管道，对水库 $i$ 的影响都是 $x_j$（根据题意）。

2. 方程组形式

我们有 $n$ 个方程（每个水库一个），$m$ 个变量（每条管道一个）。

这是一个线性方程组：$A x = c$，其中：

• $A$ 是 $n \times m$ 的矩阵
• $A_{i,j} = 1$ 如果管道 $j$ 连接水库 $i$，否则为 0
• $x$ 是 $m$ 维向量（管道流量）
• $c$ 是 $n$ 维向量（水库变化）

3. 解的性质

• 如果 $m < n$，通常无解或解不唯一
• 如果 $m = n$，可能有唯一解
• 如果 $m > n$，通常解不唯一（自由变量）

但 $A$ 有特殊结构：它是图的关联矩阵。

关键观察

1. 方程组的秩

设图的连通分量数为 $k$。

对于每个连通分量，所有方程的和为：

$$\sum_{i \in \text{component}} \sum_{j \in E_i} x_j = \sum_{i \in \text{component}} c_i $$

但每条边被计算了两次（两个端点），所以：

$$2\sum_{j \in \text{edges of component}} x_j = \sum_{i \in \text{component}} c_i $$

这是第一个约束：对于每个连通分量，$\sum c_i$ 必须是偶数。

2. 解的唯一性

方程组 $Ax = c$ 有唯一解当且仅当：

1. 解存在
2. 矩阵 $A$ 的列空间维度 = $m$（即没有自由变量）

由于 $A$ 是 $n \times m$ 的，如果 $m > n$，肯定有自由变量，解不唯一。

重要：实际上，$A$ 的秩最多为 $n-1$（因为所有行和为0的线性组合？需要检查）。

更准确：在连通图中，$A$ 的秩为 $n-1$。因为行向量之和为0（每条边被计算两次）。

3. 基环树结构

对于树（$m = n-1$）：

• 方程数 $n$ > 变量数 $n-1$
• 通常无解，除非 $c$ 满足特定条件

对于基环树（$m = n$）：

• 方程数 $n$ = 变量数 $n$
• 可能有唯一解

对于更复杂的图（$m > n$）：

• 变量多于方程，通常解不唯一

算法思路

1. 处理每个连通分量

图可能不连通，我们分别处理每个连通分量。

对于每个连通分量：

• 设它有 $n'$ 个节点，$m'$ 条边
• 如果 $m' < n'$：无解（输出0）
• 如果 $m' = n'$：基环树，可能有唯一解
• 如果 $m' > n'$：通常解不唯一（输出0）

2. 基环树情况

对于基环树（$m' = n'$），我们可以：

1. 找到环
2. 从环上断开一条边，得到一棵树
3. 在树上从叶子开始递推计算边的流量
4. 最后用环上的方程验证/计算断开边的流量

具体步骤：

// 对于基环树
1. 找到环
2. 选择环上的一条边e=(u,v)，暂时移除
3. 在树（基环树去掉e）上，以任意节点为根进行DFS
4. 对于树边，从叶子向上计算：
   x[edge] = c[node] - sum(x[child_edges])
5. 计算到根节点时，会得到关于x[e]的方程
6. 解出x[e]，验证是否整数

3. 验证解唯一性

即使对于基环树，解也可能不唯一。需要检查：

• 解出的 $x[e]$ 是否唯一
• 所有 $x_i$ 是否在 $[-10^9, 10^9]$ 范围内

完整算法

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

typedef long long ll;
const int MAXN = 100010;
const int MAXM = 500010;

int n, m;
ll c[MAXN];
vector<pair<int, int>> edges;  // 边列表
vector<int> adj[MAXN];         // 邻接表：存边编号

// 记录解
ll ans[MAXM];
bool solved = false;

// 访问标记
bool vis[MAXN];
int parent[MAXN];
int parent_edge[MAXN];

// 处理一个连通分量
bool solve_component(int start) {
    // BFS/DFS遍历整个连通分量
    vector<int> nodes;
    vector<int> comp_edges;
    
    queue<int> q;
    q.push(start);
    vis[start] = true;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        nodes.push_back(u);
        
        for (int eid : adj[u]) {
            comp_edges.push_back(eid);
            auto& e = edges[eid];
            int v = (e.first == u) ? e.second : e.first;
            if (!vis[v]) {
                vis[v] = true;
                parent[v] = u;
                parent_edge[v] = eid;
                q.push(v);
            }
        }
    }
    
    // 去重边
    sort(comp_edges.begin(), comp_edges.end());
    comp_edges.erase(unique(comp_edges.begin(), comp_edges.end()), comp_edges.end());
    
    int n_nodes = nodes.size();
    int n_edges = comp_edges.size();
    
    // 检查边数
    if (n_edges < n_nodes) {
        return false;  // 无解
    }
    if (n_edges > n_nodes) {
        return false;  // 解不唯一
    }
    
    // n_edges == n_nodes：基环树
    // 找到环
    vector<bool> in_cycle(n_nodes, false);
    vector<int> cycle_edges;
    
    // 使用DFS找环
    vector<int> color(n+1, 0);  // 0未访问，1访问中，2访问完
    vector<int> cycle_nodes;
    int cycle_start = -1;
    
    function<bool(int, int)> dfs_find_cycle = [&](int u, int p) {
        color[u] = 1;
        for (int eid : adj[u]) {
            auto& e = edges[eid];
            int v = (e.first == u) ? e.second : e.first;
            if (v == p) continue;
            if (color[v] == 1) {
                cycle_start = v;
                cycle_nodes.push_back(u);
                cycle_edges.push_back(eid);
                return true;
            } else if (color[v] == 0) {
                if (dfs_find_cycle(v, u)) {
                    if (cycle_start != -1) {
                        cycle_nodes.push_back(u);
                        cycle_edges.push_back(eid);
                        if (u == cycle_start) {
                            cycle_start = -1;  // 环闭合
                        }
                    }
                    return true;
                }
            }
        }
        color[u] = 2;
        return false;
    };
    
    dfs_find_cycle(start, -1);
    
    if (cycle_edges.empty()) {
        return false;  // 没有环，应该是树但边数=nodes，矛盾
    }
    
    // 选择环上的一条边断开
    int break_edge = cycle_edges[0];
    int u = edges[break_edge].first;
    int v = edges[break_edge].second;
    
    // 从图中临时移除这条边
    // 实际上，我们可以在计算时忽略它
    
    // 在树（基环树-break_edge）上计算
    // 以u为根进行DFS
    vector<ll> residual(n+1, 0);
    
    function<void(int, int)> dfs_tree = [&](int u, int p) {
        for (int eid : adj[u]) {
            if (eid == break_edge) continue;  // 跳过断开的边
            
            auto& e = edges[eid];
            int v = (e.first == u) ? e.second : e.first;
            if (v == p) continue;
            
            dfs_tree(v, u);
            
            // 子节点v计算完后，residual[v]是v还需要从父边获得/送出的流量
            // 实际上，对于边(u,v)，流量x应该满足：
            // 对于v：sum(x[edges incident to v]) = c[v]
            // 在树上，x(u,v) = c[v] - sum(x[other edges from v])
            
            // 我们稍后统一计算
        }
    };
    
    dfs_tree(u, -1);
    
    // 现在计算所有树边的流量
    // 我们可以用另一种方法：从叶子开始计算
    
    // 先计算每个节点的度数（不考虑break_edge）
    vector<int> deg(n+1, 0);
    for (int node : nodes) {
        for (int eid : adj[node]) {
            if (eid != break_edge) {
                deg[node]++;
            }
        }
    }
    
    // 拓扑排序：从叶子开始
    queue<int> leaf_q;
    for (int node : nodes) {
        if (deg[node] == 1 && node != u && node != v) {
            leaf_q.push(node);
        }
    }
    
    vector<bool> processed(n+1, false);
    
    while (!leaf_q.empty()) {
        int node = leaf_q.front(); leaf_q.pop();
        if (processed[node]) continue;
        
        // 找到连接node的唯一未处理边
        int target_edge = -1;
        int neighbor = -1;
        for (int eid : adj[node]) {
            if (eid == break_edge) continue;
            if (ans[eid] == 0 && !processed[edges[eid].first] && !processed[edges[eid].second]) {
                // 这条边还未赋值
                auto& e = edges[eid];
                neighbor = (e.first == node) ? e.second : e.first;
                target_edge = eid;
                break;
            }
        }
        
        if (target_edge == -1) continue;
        
        // 计算这条边的流量
        // 对于node，除了target_edge外，所有其他边都已确定
        ll sum_other = 0;
        for (int eid : adj[node]) {
            if (eid != target_edge && eid != break_edge) {
                sum_other += ans[eid];
            }
        }
        
        // c[node] = sum_other + x[target_edge]
        ans[target_edge] = c[node] - sum_other;
        
        processed[node] = true;
        deg[neighbor]--;
        if (deg[neighbor] == 1) {
            leaf_q.push(neighbor);
        }
    }
    
    // 现在只剩下u和v以及break_edge
    // 计算u和v的方程
    ll sum_u = 0, sum_v = 0;
    for (int eid : adj[u]) {
        if (eid != break_edge) {
            sum_u += ans[eid];
        }
    }
    for (int eid : adj[v]) {
        if (eid != break_edge) {
            sum_v += ans[eid];
        }
    }
    
    // 方程：
    // sum_u + x = c[u]
    // sum_v + x = c[v]  （注意：break_edge对两端影响相同）
    
    // 这两个方程必须一致
    ll x1 = c[u] - sum_u;
    ll x2 = c[v] - sum_v;
    
    if (x1 != x2) {
        return false;  // 无解
    }
    
    ans[break_edge] = x1;
    
    // 验证所有节点
    for (int node : nodes) {
        ll total = 0;
        for (int eid : adj[node]) {
            total += ans[eid];
        }
        if (total != c[node]) {
            return false;
        }
    }
    
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    
    edges.resize(m);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges[i] = {u, v};
        adj[u].push_back(i);
        adj[v].push_back(i);
    }
    
    // 初始化答案
    fill(ans, ans + m, 0);
    
    // 处理每个连通分量
    bool ok = true;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            if (!solve_component(i)) {
                ok = false;
                break;
            }
        }
    }
    
    if (ok) {
        for (int i = 0; i < m; i++) {
            cout << ans[i] << "\n";
        }
    } else {
        cout << 0 << endl;
    }
    
    return 0;
}

算法说明

1. 连通分量处理

图可能不连通，每个连通分量独立处理。

2. 基环树判定

对于每个连通分量：

• 如果边数 < 节点数：无解
• 如果边数 > 节点数：解不唯一
• 如果边数 = 节点数：基环树，可能有唯一解

3. 基环树求解

1. 找到环
2. 断开环上一条边，得到树
3. 在树上从叶子开始递推计算边流量
4. 用环上的闭合条件计算断开边的流量
5. 验证解

4. 验证解

检查是否所有节点的方程都满足，且解在范围内。

复杂度分析

• 遍历图：$O(n + m)$
• 找环：$O(n + m)$
• 拓扑排序计算：$O(n + m)$
• 总复杂度：$O(n + m)$，可以通过 $n \le 10^5, m \le 5\times10^5$

特殊情况

1. 树结构（$m = n-1$）

对于树，方程组有 $n$ 个方程，$n-1$ 个变量，通常无解。 除非 $\sum c_i = 0$（所有行加起来为0），但即使如此，解也不唯一。

2. 多个连通分量

每个连通分量必须独立有解。

3. 范围检查

解必须在 $[-10^9, 10^9]$ 范围内，但题目保证如果唯一解存在，一定在此范围内。

总结

本题的关键：

1. 建立线性方程组：每个水库的流量平衡方程
2. 图的结构分析：基环树才有可能有唯一解
3. 递推求解：在树上从叶子开始计算
4. 环上闭合条件：验证解的唯一性

算法核心是识别基环树结构并利用树的性质递推求解。