2689. 「POI2012 R1」节日 Festival 题解

问题分析

我们有 $n$ 个变量 $X_1, X_2, \ldots, X_n$，表示运动员的耗时。

两种约束：

1. 第一类：$X_a = X_b - 1$，即 $a$ 比 $b$ 少 1 秒
2. 第二类：$X_c \le X_d$，即 $c$ 不比 $d$ 长

目标：在满足所有约束的前提下，最大化不同值的数量（即 $X_i$ 中不同数值的个数）。

约束转化

1. 第一类约束

$X_a = X_b - 1$ 可以拆分为两个不等式：

• $X_a \le X_b - 1$ （即 $X_a - X_b \le -1$）
• $X_a \ge X_b - 1$ （即 $X_b - X_a \le 1$）

2. 第二类约束

$X_c \le X_d$ 等价于 $X_c - X_d \le 0$

3. 转化为差分约束系统

所有约束都可以写成 $X_u - X_v \le w$ 的形式，其中 $w$ 是整数。

这是一个差分约束系统，可以用图论建模：

• 每个变量 $X_i$ 对应一个节点
• 对于约束 $X_u - X_v \le w$，添加一条从 $v$ 到 $u$ 的有向边，权值为 $w$

图论建模

建立有向图 $G$：

1. 对于第一类约束 $X_a = X_b - 1$：

   • 添加边 $b \to a$，权值 $-1$（表示 $X_b - X_a \le -1$，即 $X_a \ge X_b + 1$）
   • 添加边 $a \to b$，权值 $1$（表示 $X_a - X_b \le 1$，即 $X_a \le X_b + 1$） 综合：$X_a = X_b + 1$ 即 $X_a = X_b - 1$？注意方向 实际上：$X_a = X_b - 1$ ⇒ $X_a \le X_b - 1$ 且 $X_a \ge X_b - 1$
   • $X_a \le X_b - 1$ ⇒ $X_a - X_b \le -1$ ⇒ 边 $b \to a$，权值 $-1$
   • $X_a \ge X_b - 1$ ⇒ $X_b - X_a \le 1$ ⇒ 边 $a \to b$，权值 $1$

2. 对于第二类约束 $X_c \le X_d$：

   • 添加边 $d \to c$，权值 $0$（表示 $X_d - X_c \le 0$）

问题求解

1. 差分约束系统的解

对于差分约束系统 $X_u - X_v \le w_{uv}$，有解当且仅当图中没有负环。

如果有解，可以求出每个 $X_i$ 的一个可行解：

• 设源点为 $s$，添加 $s$ 到所有节点的边，权值为 0
• 用 Bellman-Ford 或 SPFA 求最短路 $dist[i]$，则 $X_i = dist[i]$ 是一个可行解

2. 最大化不同值的数量

我们的目标不是求任意解，而是求不同值数量最多的解。

关键观察：

• 如果图中存在 $u$ 到 $v$ 的路径权值和为 $w$，那么 $X_u - X_v \le w$
• 如果存在 $v$ 到 $u$ 的路径权值和为 $w'$，那么 $X_v - X_u \le w'$
• 综合：$-w' \le X_u - X_v \le w$

所以 $X_u$ 和 $X_v$ 的差被限制在一个区间内。

3. 强连通分量（SCC）分析

考虑图的强连通分量：

• 在同一个 SCC 中，任意两点 $u, v$ 互相可达
• 设 $u$ 到 $v$ 的最长路径长度为 $d_{max}(u,v)$（最大权值和）
• 设 $u$ 到 $v$ 的最短路径长度为 $d_{min}(u,v)$（最小权值和，实际上是负的最大？）

实际上，对于差分约束，我们通常关心最短路（因为 $X_u - X_v \le \text{最短路径长度}$）。

但为了最大化不同值，我们想要 $X_u$ 和 $X_v$ 的差尽可能大。

重要性质： 在同一个 SCC 中，对于任意 $u, v$，有：

• $X_u - X_v \le \text{从} v \text{到} u \text{的最短路径长度}$
• $X_v - X_u \le \text{从} u \text{到} v \text{的最短路径长度}$

所以 $|X_u - X_v| \le \max(\text{最短路长度}, \text{反向最短路长度})$。

4. 每个 SCC 内部的最大值域

对于 SCC $C$，定义：

• $d_{max}(C) = \max_{u,v \in C} (\text{从} u \text{到} v \text{的最短路径长度})$ 注意：这里的最短路径是在原图上，权值可能为负

实际上，我们需要的是 SCC 内任意两点间的最长路径（最大差值）。

设 $C$ 中节点按某种顺序排列为 $v_1, v_2, \ldots, v_k$。 我们可以分配值使得：

• $X_{v_1} = 0$
• 对于 $i > 1$，$X_{v_i} = \text{从} v_1 \text{到} v_i \text{的最短路径长度}$（取最小值约束）

这样，SCC 内不同值的最大数量 = 从 $v_1$ 到各点的最短路径中不同值的数量。

但我们可以选择不同的 $v_1$ 来最大化这个数量。

5. SCC 之间的约束

不同 SCC 之间通过 DAG 的边连接。 如果 SCC $A$ 到 SCC $B$ 有边，那么 $A$ 中所有节点的值都 $\le$ $B$ 中所有节点的值加上某个常数。

由于要最大化不同值总数，我们应该让不同 SCC 的值域尽量不重叠。

算法步骤

1. 建图

// 建立差分约束图
// 对于约束 X_a = X_b - 1：
//   add_edge(b, a, -1)  // X_b - X_a <= -1
//   add_edge(a, b, 1)   // X_a - X_b <= 1
// 对于约束 X_c <= X_d：
//   add_edge(d, c, 0)   // X_d - X_c <= 0

2. 检测负环

用 SPFA 检测图中是否有负环。如果有，输出 NIE。

3. 求强连通分量

用 Kosaraju 或 Tarjan 算法求 SCC。

4. 计算每个 SCC 内的最大不同值数

对于每个 SCC $C$：

1. 对 $C$ 中的节点，求所有点对之间的最短路径（由于 $n \le 600$，可以用 Floyd-Warshall）
2. 找到 $C$ 中任意两点之间的最大距离 $max\_dist$
3. 这个 SCC 内最多可以有 $max\_dist + 1$ 个不同的值 （因为最小值和最大值相差 $max\_dist$，中间可以有这么多整数）

但注意：如果 SCC 中有负环？实际上，如果整个图没有负环，每个 SCC 内部也没有负环。

5. 合并 SCC

由于 SCC 之间形成 DAG，我们可以按拓扑序处理。 每个 SCC 的值域可以平移，使得不同 SCC 的值不重叠，从而最大化不同值总数。

总答案 = 所有 SCC 的最大不同值数之和。

详细实现

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

const int INF = 1e9;
const int MAXN = 605;

int n, m1, m2;
int dist[MAXN][MAXN];  // Floyd-Warshall距离矩阵
vector<int> scc[MAXN];  // 每个SCC包含的节点
int scc_id[MAXN];       // 每个节点所属的SCC编号
int scc_cnt;            // SCC数量
bool in_stack[MAXN];
int low[MAXN], dfn[MAXN], dfs_clock;
stack<int> st;

// Tarjan算法求SCC
void tarjan(int u, vector<int> adj[]) {
    low[u] = dfn[u] = ++dfs_clock;
    st.push(u);
    in_stack[u] = true;
    
    for (int v : adj[u]) {
        if (!dfn[v]) {
            tarjan(v, adj);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    
    if (low[u] == dfn[u]) {
        int v;
        do {
            v = st.top(); st.pop();
            in_stack[v] = false;
            scc_id[v] = scc_cnt;
            scc[scc_cnt].push_back(v);
        } while (v != u);
        scc_cnt++;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m1 >> m2;
    
    // 初始化距离矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = INF;
        }
    }
    
    // 读入第一类约束：X_a = X_b - 1
    for (int i = 0; i < m1; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;  // 转为0-based
        
        // X_a = X_b - 1 等价于：
        // X_a <= X_b - 1 和 X_a >= X_b - 1
        // 即：X_a - X_b <= -1 和 X_b - X_a <= 1
        dist[b][a] = min(dist[b][a], -1);  // X_b - X_a <= -1
        dist[a][b] = min(dist[a][b], 1);   // X_a - X_b <= 1
    }
    
    // 读入第二类约束：X_c <= X_d
    for (int i = 0; i < m2; i++) {
        int c, d;
        cin >> c >> d;
        c--; d--;
        
        // X_c <= X_d 等价于 X_c - X_d <= 0
        dist[d][c] = min(dist[d][c], 0);  // X_d - X_c <= 0
    }
    
    // Floyd-Warshall求所有点对最短路
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (dist[i][k] == INF) continue;
            for (int j = 0; j < n; j++) {
                if (dist[k][j] == INF) continue;
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    // 检查负环：如果dist[i][i] < 0，存在负环
    for (int i = 0; i < n; i++) {
        if (dist[i][i] < 0) {
            cout << "NIE" << endl;
            return 0;
        }
    }
    
    // 构建原图（用于求SCC）
    vector<int> adj[n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && dist[i][j] < INF) {
                adj[i].push_back(j);
            }
        }
    }
    
    // 求强连通分量
    memset(dfn, 0, sizeof(dfn));
    memset(in_stack, 0, sizeof(in_stack));
    dfs_clock = scc_cnt = 0;
    for (int i = 0; i < n; i++) {
        if (!dfn[i]) {
            tarjan(i, adj);
        }
    }
    
    // 计算每个SCC内的最大不同值数
    vector<int> scc_max_diff(scc_cnt, 0);
    
    for (int comp = 0; comp < scc_cnt; comp++) {
        // 获取该SCC的所有节点
        vector<int>& nodes = scc[comp];
        int sz = nodes.size();
        
        if (sz == 1) {
            scc_max_diff[comp] = 1;  // 只有一个节点，只有1个值
            continue;
        }
        
        // 计算SCC内所有点对的最大距离
        int max_diff = 0;
        for (int i = 0; i < sz; i++) {
            for (int j = 0; j < sz; j++) {
                int u = nodes[i], v = nodes[j];
                if (dist[u][v] < INF) {
                    max_diff = max(max_diff, dist[u][v]);
                }
            }
        }
        
        // 最大不同值数 = 最大距离 + 1
        scc_max_diff[comp] = max_diff + 1;
    }
    
    // 计算总答案：所有SCC的最大不同值数之和
    int ans = 0;
    for (int comp = 0; comp < scc_cnt; comp++) {
        ans += scc_max_diff[comp];
    }
    
    cout << ans << endl;
    
    return 0;
}

算法正确性证明

1. 负环检测

如果图中存在负环，差分约束系统无解，输出 NIE。

2. SCC内最大不同值数

对于 SCC $C$，设其中两点 $u, v$ 的最短路径长度为 $d_{uv}$（从 $u$ 到 $v$ 的最小约束）。 那么 $X_v - X_u \le d_{uv}$。

我们可以构造一组解：

• 固定 SCC 中某个参考点 $r$，设 $X_r = 0$
• 对于其他点 $v$，设 $X_v = \min_{u \in C} (X_u + d_{uv})$ 的最紧约束

实际上，我们可以让 SCC 中所有点的值分布在区间 $[0, max\_dist]$ 内，其中 $max\_dist = \max_{u,v \in C} d_{uv}$。 这样最多可以有 $max\_dist + 1$ 个不同的整数值。

3. SCC间不重叠

由于 SCC 之间形成 DAG，我们可以按拓扑序给每个 SCC 分配值域区间，使它们互不重叠。 这样不同 SCC 的值不会重复，总不同值数就是各 SCC 不同值数之和。

复杂度分析

1. Floyd-Warshall：$O(n^3)$，$n \le 600$，$600^3 = 2.16 \times 10^8$，可能较大但应该能过（时限 100-7500ms）
2. Tarjan 求 SCC：$O(n + m)$，$m$ 是边数
3. 总复杂度主要由 Floyd-Warshall 决定

优化

对于 $n=600$，$O(n^3)$ 的 Floyd-Warshall 可能较慢。可以优化：

• 使用 Johnson 算法：$O(nm \log n)$，但 $m$ 可达 $100,000$，$600 \times 100,000 = 6 \times 10^7$，可能更快
• 或者对每个 SCC 分别运行 Floyd-Warshall，因为 SCC 通常较小

样例验证

输入：

4 2 2
1 2
3 4
1 4
3 1

约束：

1. $X_1 = X_2 - 1$
2. $X_3 = X_4 - 1$
3. $X_1 \le X_4$
4. $X_3 \le X_1$

建图：

• 边：2→1(-1), 1→2(1), 4→3(-1), 3→4(1), 4→1(0), 1→3(0)

计算后得到答案 3。

总结

本题的关键：

1. 差分约束建模：将等式和不等式转化为图
2. 负环检测：确保解存在
3. 强连通分量分析：SCC 内部的值域范围
4. 最大化不同值：每个 SCC 内尽可能分散，SCC 间不重叠

核心算法：Floyd-Warshall + Tarjan SCC，时间复杂度 $O(n^3)$，对于 $n \le 600$ 可接受。