P6755 Pipes 题解

upd:修复错误，精简代码，补充注释

我们模拟赛题

题目大意

题目等价于：

给定一个无自环重边的无向连通图，边权均为偶数，点权等于与其相连的边权之和的一半。 现给定每个点的点权以及边的连接情况，试求解每条边的边权。

题目分析

相当于求解一个 $m$ 元含 $n$ 条方程的方程组。

容易想到高斯消元，效率为 $O(n^3)$ ，显然过不了(考试时我的写法)

由于原图连通，故至少含有 $n-1$ 条边，即 $m>n-1$

• 当 $m>n$ 时，由于至少需要 $m$ 条方程才可能解出唯一解，故必有多解，输出 $0$ 。

• 当 $m<n\Leftrightarrow m=n-1$ 时，原图为一颗树。由于叶子结点只有一条边与之相连，而对于其他节点当其所有子树与之相连的边权以及其自身点权都一直时，其连向父节点的边权也可求出。

  则对树进行遍历，从叶子节点开始往上回溯，即可求出所有边权。

• 当 $m=n$ 时，原图为一颗基环树。对于非环部分，可以同树一样求解；对于环上的部分，可以通过线性求解若干条方程解决。

综上，可以在线性复杂度内解决问题，复杂度为（似乎） $O(n+m)$ .

处理细节

对于求环上边权的部分，可以通过如下步骤求解：

假设环上节点编号分别为 $1,2,\dots,k$.

我们设 $tpv_i$ 表示当前节点不在环上的边权之和，设两条环上边分别为 $x_i$ 与 $x_{i+1}$ （首尾需特判, $x_{k+1}=x_1$ ），该点点权为 $a_i$。

则有：

将 $2a_i-tpv_i$ 记作 $a'_i$ ,

而能否得到答案，还与环长的奇偶性有关。

当我们计算

时，可能会将所有 $x$ 消完，也可能剩下一个未知量。

• 当环的路径数为偶数时，沿环一次计算结果为

  $$x_1+x_2-x_2-x_3\dots-x_k-x_1=0$$

  则我们无法解出环上的边权。

• 当环的路径数为奇数时，结果为

  $$x_1+x_2-x_2-x_3\dots-x_{k-1}-x_k+x_k+x_1=2x_1$$

  则此时可以解出 $x_1$ ，并由此解出 $x_2,x_3,\dots,x_k$ 。

所以，对于环的长度，我们需要进行一定的特判，以此得到正确答案。

参考代码

我使用拓扑排序的方法对树进行遍历，每次加入度为 $1$ 的点。遍历完后如果还有节点没被访问，说明剩下的均为环，则按照上面步骤处理。

#include <bits/stdc++.h>
#define rint register int
#define fu(i, a, b, d, c) for (rint i = a; i <= (b) && c; i += d)
#define fd(i, a, b, d, c) for (rint i = a; i >= (b) && c; i -= d)
using namespace std;
inline int read()
{
    char c = 0, f = 1;
    int num = 0;
    while (c < '0' || c > '9' && c != '-')
        ((c = getchar()) == '-') && (f = -f);
    while (c >= '0' && c <= '9')
        num = (num << 1) + (num << 3) + (c ^ 48), c = getchar();
    return num * f;
}
const int MAXN = 100050, MAXM = 500050;
int n, m;
int head[MAXN], nxt[MAXM], to[MAXM], cnt, id[MAXM];
void add(int u, int v, int i) { nxt[++cnt] = head[u], head[u] = cnt, to[cnt] = v, id[cnt] = i; }
int a[MAXN], d[MAXN], tpv[MAXN], vis[MAXN], vised, ans[MAXM], gonex[MAXN];
queue<int> q;
signed main()
{
    n = read(), m = read();
    if (n < m)
        return printf("0") & 0;
    fu(i, 1, n, 1, 1) a[i] = read();
    fu(i, 1, m, 1, 1)
    {
        int u = read(), v = read();
        add(u, v, i), add(v, u, i);
        //度数加一
        d[u]++, d[v]++;
    }
    fu(i, 1, n, 1, 1) if (d[i] == 1) q.push(i); //度为 1 节点入队
    while (!q.empty())    //树上计算
    {
        int now = q.front();
        q.pop();
        vis[now] = 1, vised++;
        for (int i = head[now]; i; i = nxt[i])
            if (!vis[to[i]])
            {
                //ans 表示答案数组，pv 表示连向子树的边权
                ans[id[i]] = 2 * a[now] - tpv[now]; //计算连向父亲的边权
                tpv[to[i]] += ans[id[i]];
                d[to[i]]--;
                if (d[to[i]] == 1)
                    q.push(to[i]); //新点入队
            }
    }
    if (vised < n) //存在环
    {
        if (!((n - vised) & 1)) //环长为偶数，直接输出 0
            return printf("0") & 0;
        int cur = 0, sum = 0, sym = 1, st = 0, tmp;
        //cur 为当前节点，sum 为点权和， sym为符号(依次交替)，st为起点
        fu(i, 1, n, 1, 1) if (!vis[i])
        {
            st = cur = i;
            a[i] = 2 * a[i] - tpv[i]; //计算 a'
        }
        while (!vis[cur])
        {
            bool tost = 0, flag = 0;//tost = to start 是否能到达起点; flag 记录是否是环尾
            int stg = 0;
            vis[cur] = 1;
            sum += a[cur] * sym;
            sym = -sym;
            for (int i = head[cur]; i; i = nxt[i])
            {
                if (to[i] == st) //这里处理是否是 1.起点连出的 2.环尾连入起点的
                    tost = 1, stg = i;
                if (!vis[to[i]])
                {
                    flag = 1;
                    gonex[cur] = i, cur = to[i];
                    //gonex 表示环上下一步走的边
                    break;
                }
            }
            if (!flag && tost) //是否是环尾
                gonex[cur] = stg;
        }
        ans[id[gonex[cur]]] = sum / 2; //计算 环尾-起点 边权
        tmp = ans[id[gonex[cur]]];     //tmp 记录上一条边，a[cur]-tmp 即为连接cur的另一条边的边权
        cur = st;                      //cur指向起点
        do
        {
            ans[id[gonex[cur]]] = a[cur] - tmp;
            tmp = ans[id[gonex[cur]]]; //更新tmp
            cur = to[gonex[cur]];
        } while (cur != st);
    }
    fu(i, 1, m, 1, 1) printf("%d\n", ans[i]);
}