题解：有向图点权调整问题

题目分析

问题描述

给定一个有向弱连通图，每个点有：

• 初始点权 $d_i$
• 修改耗时 $w_i$（每单位改变量的代价）

要求通过调整点权（可以加1或减1），使得对于每条有向边 $(u,v)$ 都满足 $d_u \leq d_v$，并且总修改耗时最小。

关键观察

1. 约束条件分析：

   • 对于每条边 $u \to v$，要求 $d_u \leq d_v$
   • 这意味着如果存在路径 $u \to v$，那么 $d_u \leq d_v$
   • 特别地，如果存在环，那么环上所有点的值必须相等

2. 图的结构：

   • 弱连通图：将边视为无向边时图是连通的
   • 可能包含环，也可能包含链
   • 需要处理环上的特殊约束

3. 优化思路：

   • 最终每个点的值一定是某个初始点权（离散化后）
   • 对于树结构，可以用树形DP
   • 对于环，需要破环为链，考虑环上相邻点的约束

算法设计

1. 离散化

将所有可能的点权值离散化，减少状态空间。

2. 整体二分框架

使用类似"整体二分"的方法，将点按最终取值划分，通过位标记管理划分过程。

3. 环处理

• 检测图中的环
• 对环上的点进行特殊DP处理：
  • 破环为链，考虑两种起始状态
  • 计算环上最优赋值方案

4. 树形DP

对于非环部分，使用树形DP计算最小代价，根据边方向决定状态转移。

代码实现

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

const int MXN = 300000;
const long long INF = 0x3f3f3f3f3f3f3f3f;

int n, m, d[MXN], w[MXN];
long long ns;
struct edge {
    int v, t;  // v: 目标点, t: 类型(0:反向边, 1:正向边)
};
vector<edge> g[MXN];
vector<int> nums;
int res[MXN], q[MXN], ql[MXN], qr[MXN], x, clr[MXN];
long long f[MXN][2], dp[2][MXN][2];
bool found_loop, is_loop, on_loop[MXN], visited[MXN];
vector<edge> loop;

// 寻找环
void fnd_loop(int u, int fa) {
    visited[u] = 1;

    for (auto x : g[u]) {
        int v = x.v, t = x.t;

        if (clr[v] != clr[u] || v == fa)
            continue;

        if (visited[v])
            found_loop = is_loop = 1;
        else
            fnd_loop(v, u);

        if (is_loop) {
            loop.push_back({v, t});
            break;
        }
    }

    if (is_loop && u == loop[0].v)
        is_loop = 0;
}

// 树形DP计算代价
void dfs(int u, int fa) {
    visited[u] = 1;
    f[u][0] = (long long)w[u] * abs(nums[x] - d[u]);      // 当前值
    f[u][1] = (long long)w[u] * abs(nums[x] + 1 - d[u]);  // 下一个值

    for (auto x : g[u]) {
        int v = x.v, t = x.t;

        if (clr[v] != clr[u] || v == fa || on_loop[v])
            continue;

        dfs(v, u);

        if (t) {  // 正向边 u->v
            f[u][0] += f[v][0];
            f[u][1] += min(f[v][0], f[v][1]);
        } else {  // 反向边 v->u  
            f[u][0] += min(f[v][0], f[v][1]);
            f[u][1] += f[v][1];
        }
    }
}

// 确定每个点的最终选择
void query(int u, int i, int fa) {
    res[u] = i;

    for (auto x : g[u]) {
        int v = x.v, t = x.t;

        if (clr[v] != clr[u] || v == fa || on_loop[v])
            continue;

        if (t)
            if (i)
                query(v, f[v][0] > f[v][1], u);
            else
                query(v, 0, u);
        else if (i)
            query(v, 1, u);
        else
            query(v, f[v][0] > f[v][1], u);
    }
}

// 整体二分求解
void solve(int l, int r, int L, int R, int dep) {
    int i, j, k;

    if (L == R) {
        for (i = l; i <= r; ++i)
            res[q[i]] = L;
        return;
    }

    x = L + R >> 1;  // 中间值

    // 初始化标记
    for (i = l; i <= r; ++i)
        on_loop[q[i]] = visited[q[i]] = 0;

    // 处理每个连通分量
    for (i = l; i <= r; ++i)
        if (!visited[q[i]]) {
            loop.clear();
            found_loop = 0;
            fnd_loop(q[i], -1);

            if (found_loop) {  // 处理环
                // 标记环上点
                for (auto x : loop)
                    on_loop[x.v] = 1;

                // 计算环上每个点的DP值
                for (auto x : loop)
                    dfs(x.v, -1);

                // 破环为链，考虑两种起始状态
                dp[0][0][0] = f[loop[0].v][0];
                dp[0][0][1] = INF;
                dp[1][0][0] = INF;
                dp[1][0][1] = f[loop[0].v][1];

                // DP计算环上最优解
                for (i = 0; i < 2; ++i)
                    for (j = 1; j < loop.size(); ++j) {
                        int v = loop[j].v, t = loop[j - 1].t;

                        if (t) {  // 正向边
                            dp[i][j][0] = f[v][0] + dp[i][j - 1][0];
                            dp[i][j][1] = f[v][1] + min(dp[i][j - 1][0], dp[i][j - 1][1]);
                        } else {  // 反向边
                            dp[i][j][0] = f[v][0] + min(dp[i][j - 1][0], dp[i][j - 1][1]);
                            dp[i][j][1] = f[v][1] + dp[i][j - 1][1];
                        }
                    }

                // 根据最后一条边决定最优解
                if (loop.back().t) {  // 最后是正向边
                    long long mn = min(dp[0][loop.size() - 1][0], 
                                     min(dp[1][loop.size() - 1][0], dp[1][loop.size() - 1][1]));

                    if (mn == dp[0][loop.size() - 1][0])
                        i = k = 0;
                    else if (mn == dp[1][loop.size() - 1][0]) {
                        i = 1;
                        k = 0;
                    } else
                        i = k = 1;
                } else {  // 最后是反向边
                    long long mn = min(dp[0][loop.size() - 1][0], 
                                     min(dp[0][loop.size() - 1][1], dp[1][loop.size() - 1][1]));

                    if (mn == dp[0][loop.size() - 1][0])
                        i = k = 0;
                    else if (mn == dp[0][loop.size() - 1][1]) {
                        i = 0;
                        k = 1;
                    } else
                        i = k = 1;
                }

                // 回溯确定环上每个点的选择
                for (j = loop.size() - 1;; --j) {
                    int v = loop[j].v, t = loop[j - 1].t;
                    query(v, k, -1);

                    if (j == 0)
                        break;

                    if (t) {
                        if (k)
                            k = dp[i][j - 1][0] > dp[i][j - 1][1];
                    } else if (k == 0)
                        k = dp[i][j - 1][0] > dp[i][j - 1][1];
                }
            } else {  // 处理树
                dfs(q[i], -1);
                query(q[i], f[q[i]][0] > f[q[i]][1], -1);
            }
        }

    // 根据选择划分点集
    for (i = l, j = -1, k = -1; i <= r; ++i)
        if (res[q[i]]) {
            clr[q[i]] ^= 1 << dep;  // 更新颜色标记
            qr[++k] = q[i];
        } else
            ql[++j] = q[i];

    // 重新排列点
    for (i = 0; i <= j; ++i)
        q[i + l] = ql[i];
    for (i = 0; i <= k; ++i)
        q[i + l + j + 1] = qr[i];

    // 递归处理两个子集
    solve(l, l + j, L, L + R >> 1, dep + 1);
    solve(l + j + 1, r, (L + R >> 1) + 1, R, dep + 1);
}

int main() {
    int i;
    scanf("%d%d", &n, &m);

    // 读入点权和权重
    for (i = 0; i < n; ++i) {
        scanf("%d", &d[i]);
        nums.push_back(d[i]);
    }

    // 离散化
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    for (i = 0; i < n; ++i)
        scanf("%d", &w[i]);

    // 建图（双向，标记边类型）
    for (i = 0; i < m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[--u].push_back({--v, 0});  // 正向边
        g[v].push_back({u, 1});      // 反向边
    }

    // 初始化点集
    for (i = 0; i < n; ++i)
        q[i] = i;

    // 求解
    solve(0, n - 1, 0, nums.size() - 1, 0);

    // 计算总代价
    for (i = 0; i < n; ++i)
        ns += (long long)w[i] * abs(d[i] - nums[res[i]]);

    printf("%lld", ns);
    return 0;
}

算法总结

时间复杂度：$O(n \log n)$，主要来自整体二分和离散化
空间复杂度：$O(n + m)$

核心技巧

1. 离散化减少状态空间
2. 整体二分框架处理最优赋值
3. 环检测与破环DP处理环约束
4. 树形DP处理树结构

难点

• 环的特殊处理需要仔细考虑边界条件
• 整体二分的划分策略
• 状态转移方程的推导

这道题综合了图论、动态规划和分治算法的多个技巧，是一道很有挑战性的题目。