PA 2019 Runda 4 Wyspa 题解

题目分析

这道题要求计算选择港口的方案数，使得所有湖边点都能到达至少一个港口。这是一个平面图上的可达性覆盖问题。

关键约束：

• 图是平面图，具有平面嵌入性质
• 湖边点和海边点分别按环状排列
• 需要覆盖所有湖边点的可达性需求

解题思路

核心观察

1. 平面图性质：由于是平面图，可以找到特定的环状结构
2. 强连通分量：通过缩点简化图结构
3. 区间覆盖：将海边点映射到环上的区间，问题转化为区间覆盖

算法框架

代码采用了Tarjan缩点 + 区间处理 + 动态规划的方法：

主要步骤：

1. 强连通分量分解：使用Tarjan算法缩点
2. 区间提取：为每个SCC计算对应的海边点覆盖区间
3. 区间化简：去除被包含的冗余区间
4. 环展开：将环状结构展开为线性序列
5. 动态规划：计算覆盖整个环的方案数

代码详解

#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long ll;
const int N = 5e5 + 5;
const int Mod = 1e9 + 7;

int n, m, a, b;
int dfn[N], low[N], sd[N], stk[N], top, id[N];
int L[N], R[N], mxL[N * 2], mxLL[N * 2];
int ans, f[N * 2], s[N * 2];
ll pw2[N];
bool instk[N], lk[N], ban[N];

vector<int> G[N], G1[N];

// Tarjan算法求强连通分量
void Tarjan(int x) {
    dfn[x] = low[x] = ++dfn[0];
    stk[++top] = x;
    instk[x] = 1;

    for (auto v : G[x]) {
        if (!dfn[v]) {
            Tarjan(v);
            low[x] = min(low[x], low[v]);
        } else if (instk[v])
            low[x] = min(low[x], dfn[v]);
    }

    if (dfn[x] == low[x]) {
        sd[0]++;
        do {
            instk[stk[top]] = 0;
            sd[stk[top]] = sd[0];
        } while (stk[top--] != x);
    }
}

vector<pair<int, int>> tmp, seg, pre[N];

// 合并区间
inline void calc(int x) {
    if (tmp.empty()) return;
    
    sort(tmp.begin(), tmp.end());
    auto p = tmp.begin() + 1;
    int mx = tmp.begin()->second;
    
    while (p != tmp.end()) {
        if (p->first > mx + 1) break;
        mx = max(mx, p->second);
        p++;
    }
    
    if (p == tmp.end()) {
        L[x] = tmp.begin()->first;
        R[x] = mx;
    } else {
        R[x] = mx;
        L[x] = p->first;
    }
    
    vector<pair<int, int>>().swap(tmp);
}

// DFS计算每个SCC的覆盖区间
void dfs(int x) {
    if (L[x]) return;
    
    L[x] = -1;
    for (auto v : G1[x]) dfs(v);
    
    // 收集子节点的区间
    for (auto v : G1[x]) {
        if (L[v] == -1) continue;
        if (L[v] <= R[v])
            tmp.eb(L[v], R[v]);
        else
            tmp.eb(L[v], id[0]), tmp.eb(1, R[v]);
    }
    
    tmp.insert(tmp.end(), pre[x].begin(), pre[x].end());
    calc(x);
}

算法原理详解

1. 图收缩与区间表示

• Tarjan缩点：将强连通分量合并为超级节点
• 区间表示：每个SCC对应一个海边点的覆盖区间 [L, R]
• 环状处理：当 L > R 时表示区间跨越了环的起点

2. 区间化简

// 去除被包含的区间
sort(ttmp.begin(), ttmp.end(), [](info a, info b) {
    return a.l == b.l ? a.r == b.r ? a.id > b.id : a.r > b.r : a.l < b.l;
});

auto p = ttmp.rbegin();
int mn = 1e9;
while (p != ttmp.rend()) {
    if (p->r >= mn) ban[p->id] = 1;
    mn = min(mn, p->r);
    p++;
}

3. 动态规划计算方案数

for (int i = 2; i <= R[mnid]; i++) {
    f[i] = s[i] = pw2[H[i] - H[i - 1]] - 1;
    int mxcur = 1;
    
    for (int j = i + 1; j <= H.cnt; j++) {
        f[j] = (s[j - 1] - s[mxcur] + Mod) * (pw2[H[j] - H[j - 1]] - 1) % Mod;
        s[j] = (s[j - 1] + f[j]) % Mod;
        mxcur = max(mxcur, mxL[j]);
    }
    
    ans = (ans + (ll)(s[H.cnt] - s[mxcur] + Mod)) % Mod;
    s[i] = 0;
    mxL[H.cnt] = max(mxL[H.cnt], mxLL[i]);
}

关键技巧

1. 环展开技术

将环状结构复制一份接在末尾，转化为线性问题：

if (L[i] <= R[i])
    ttmp.eb(L[i], R[i], i), ttmp.eb(id[0] + L[i], id[0] + R[i], i);
else
    ttmp.eb(L[i], id[0] + R[i], i);

2. 离散化优化

使用哈希表将大范围坐标映射到紧凑索引：

struct Hash {
    int val[N], cnt;
    void add(int x) { val[++cnt] = x; }
    void init() { 
        sort(val + 1, val + cnt + 1);
        cnt = unique(val + 1, val + cnt + 1) - val - 1;
    }
    int v(int x) { 
        return lower_bound(val + 1, val + cnt + 1, x) - val; 
    }
} H;

3. 幂次预处理

预先计算2的幂次模结果：

pw2[0] = 1;
for (int i = 1; i <= n; i++)
    pw2[i] = pw2[i - 1] * 2 % Mod;

复杂度分析

• 时间复杂度：$O(n + m)$，主要来自Tarjan和DFS
• 空间复杂度：$O(n + m)$，存储图结构和中间结果

样例解析

样例1

输入: 6 8 3 3

图结构使得6号点必须选，4、5号点可选，方案数为4。

样例2

输入: 8 7 3 4

通过区间合并和DP计算得到8种方案。

总结

这道题的解题亮点：

1. 平面图性质利用：通过环状结构简化问题
2. 图收缩技术：使用SCC缩点降低问题规模
3. 区间覆盖模型：将图覆盖问题转化为区间覆盖
4. 环展开技巧：处理环状结构的经典方法
5. 动态规划优化：高效计算覆盖方案数

算法综合运用了图论、组合数学和动态规划，展示了解决复杂几何图论问题的有效方法。