题目分析

Alice 和 Bob 需要在岛屿间进行往返旅行，但危桥有通行次数限制。需要判断是否存在方案同时满足两人的往返需求。

关键约束：

• 危桥最多通行 2 次
• 普通桥可无限次通行
• 两人路径不能冲突

解题思路

核心思想

使用网络流建模：

• 将岛屿作为节点，桥梁作为边
• 危桥容量为2，普通桥容量无限
• 使用最大流算法检查是否满足流量需求

关键技术

• ISAP算法：高效的最大流算法
• 多源多汇：通过超级源点和汇点处理多人需求
• 对称性验证：交换起点终点验证双向可行性

算法步骤

1. 构建网络流图：岛屿为节点，桥梁为边
2. 设置容量：危桥容量2，普通桥容量无穷
3. 添加需求边：连接源点到起点，终点到汇点
4. 计算最大流：使用ISAP算法
5. 对称验证：交换Bob的起点终点再次验证
6. 输出结果：两次验证都通过则输出"Yes"

完整代码

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

typedef long long ll;

const ll INF = 1e18;
const int MAXN = 55;

int n;                    // 岛屿数量
int el;                   // 边计数器
int s, t;                 // 超级源点和汇点
int as, at, an;           // Alice的起点、终点、往返次数
int bs, bt, bn;           // Bob的起点、终点、往返次数
int u, v;                 // 临时变量
ll w, ans;                // 权重和答案

// 图结构
int head[MAXN];           // 头指针数组
int current[MAXN];        // 当前弧优化
int depth[MAXN];          // 深度数组
int gap[MAXN];            // 间隙数组
queue<int> q;             // BFS队列
char bridge[MAXN][MAXN];  // 桥梁矩阵

// 边结构
struct Edge {
    int to, next;
    ll capacity;
    Edge(int _to = 0, int _next = 0, ll _capacity = 0) {
        to = _to;
        next = _next;
        capacity = _capacity;
    }
} edges[2505];  // 边数组

// 添加边
inline void addEdge(int from, int to, ll capacity) {
    edges[++el] = Edge(to, head[from], capacity);
    head[from] = el;
}

// DFS进行增广
inline ll dfs(int u, ll flow) {
    if (u == t) {
        ans += flow;
        return flow;
    }

    ll used = 0;
    
    // 当前弧优化
    for (int& i = current[u]; i != -1; i = edges[i].next) {
        int v = edges[i].to;
        
        // 只能向深度更小的节点流动
        if (edges[i].capacity > 0 && depth[v] + 1 == depth[u]) {
            ll pushed = dfs(v, min(flow - used, edges[i].capacity));
            
            if (pushed > 0) {
                edges[i].capacity -= pushed;
                edges[i ^ 1].capacity += pushed;
                used += pushed;
                
                if (used == flow) {
                    return used;
                }
            }
        }
    }
    
    // 间隙优化
    gap[depth[u]]--;
    if (gap[depth[u]] == 0) {
        depth[s] = n + 3;  // 标记源点不可达
    }
    
    depth[u]++;
    gap[depth[u]]++;
    
    return used;
}

// ISAP算法计算最大流
inline ll computeMaxFlow() {
    // 初始化
    memset(head, -1, sizeof(head));
    memset(gap, 0, sizeof(gap));
    memset(depth, -1, sizeof(depth));
    el = 1;  // 从1开始，方便异或操作
    ans = 0;
    
    // 构建桥梁边
    for (int i = 1; i <= n; i++) {
        for (int j = i; j < n; j++) {
            if (bridge[i][j] != 'X') {
                // 危桥容量为2，普通桥容量无限
                w = (bridge[i][j] == 'N' ? INF : 2LL);
                addEdge(i, j + 1, w);
                addEdge(j + 1, i, w);
            }
        }
    }
    
    // 添加需求边
    // Alice的需求：从s到as流量an，从at到t流量an
    addEdge(s, as, an);
    addEdge(as, s, 0);
    addEdge(t, at, an);
    addEdge(at, t, 0);
    
    // Bob的需求：从s到bs流量bn，从bt到t流量bn
    addEdge(s, bs, bn);
    addEdge(bs, s, 0);
    addEdge(t, bt, bn);
    addEdge(bt, t, 0);
    
    // BFS预处理深度
    depth[t] = 0;
    gap[0] = 1;
    q.push(t);
    
    while (!q.empty()) {
        u = q.front();
        q.pop();
        
        for (int i = head[u]; i != -1; i = edges[i].next) {
            v = edges[i].to;
            if (depth[v] == -1) {
                depth[v] = depth[u] + 1;
                gap[depth[v]]++;
                q.push(v);
            }
        }
    }
    
    // 多路增广
    while (depth[s] < n + 2) {
        memcpy(current, head, sizeof(head));
        dfs(s, INF);
    }
    
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    // 处理多组测试数据
    while (cin >> n >> as >> at >> an >> bs >> bt >> bn) {
        // 调整索引（题目从0开始，代码从1开始）
        as++; at++; bs++; bt++;
        s = 0;          // 超级源点
        t = n + 1;      // 超级汇点
        
        // 读入桥梁矩阵
        for (int i = 1; i <= n; i++) {
            cin >> bridge[i];
        }
        
        // 第一次检查：正常路径
        ll flow1 = computeMaxFlow();
        
        // 第二次检查：交换Bob的起点终点（验证对称性）
        swap(bs, bt);
        ll flow2 = computeMaxFlow();
        
        // 判断结果
        if (flow1 == an + bn && flow2 == an + bn) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
    
    return 0;
}

代码说明

关键数据结构

• Edge结构：存储边的终点、下一条边、容量
• head[]数组：邻接表头指针
• depth[]数组：BFS深度，用于分层图
• gap[]数组：间隙优化，加速算法

算法核心

1. 网络流建模

节点安排：

• 0: 超级源点 (s)
• 1~n: 岛屿节点
• n+1: 超级汇点 (t)

边容量设置：

w = (bridge[i][j] == 'N' ? INF : 2LL);

• 'N'（普通桥）：无限容量
• 'O'（危桥）：容量2
• 'X'（无桥）：不连接

2. ISAP算法优化

当前弧优化：

for (int& i = current[u]; i != -1; i = edges[i].next)

避免重复检查已经处理过的边。

间隙优化：

gap[depth[u]]--;
if (gap[depth[u]] == 0) {
    depth[s] = n + 3;  // 提前终止
}

当某一深度没有节点时，可以提前终止算法。

3. 对称性验证

// 第一次检查
ll flow1 = computeMaxFlow();

// 第二次检查：交换Bob的起点终点  
swap(bs, bt);
ll flow2 = computeMaxFlow();

需要两次验证确保往返路径在两个方向都可行。

数学原理

最大流最小割定理：如果最大流等于需求流量，说明存在满足条件的路径方案。

往返次数转换：一次往返需要从起点到终点再返回，在网络流中对应从源点到起点、终点到汇点的流量需求。

复杂度分析

• 节点数：n + 2 ≤ 52
• 边数：最多 O(n²) = 2500
• ISAP复杂度：O(V²E)，但优化后实际运行很快
• 总复杂度：在数据范围内完全可行