题目分析

在一个棋盘游戏 $\text{Risk}$ 中，玩家控制若干区域，每个区域有若干军队。玩家可以在自己控制的相邻区域之间移动军队，移动过程中每个区域必须始终至少保留一个军队。目标是经过一个回合的移动后，使得所有与对手区域相邻的我方区域（称为边界区域）中，军队数量的最小值尽可能大。

换句话说，我们需要最大化一个值 $target$，使得存在一种移动方案，让每个边界区域的军队数都至少达到 $target$，同时满足移动过程中的约束。

解题思路

这是一个典型的最大值最小化问题，通常可以用二分答案 + 可行性检查的方法解决。

二分答案框架

• 下界 $low$：初始时所有边界区域军队数量的最小值。
• 上界 $high$：我方所有军队的总数（因为军队不可能超过总数）。
• 在 $[low,high]$ 范围内二分查找，对于每个 $mid$，判断是否能让所有边界区域的军队数都 $\ge mid$。

可行性检查的核心难点

移动军队时有两个关键约束：

1. 每个区域在任何时刻至少保留一个军队。
2. 军队只能在自己控制的相邻区域间移动。

直接模拟移动过程非常复杂，我们需要一个数学模型来描述军队的重新分配。

网络流建模

本题的标准解法是使用最大流来检查可行性。建模的关键在于如何正确表示军队的流动和最终分布。

拆点技巧

每个我方区域 $i$ 拆成两个节点：

• 入点 $i$：表示区域本身
• 出点 $i+n$：表示从该区域流出的军队

为什么需要拆点？
拆点可以精确控制每个区域的军队数量：区域 $i$ 最终的军队数 = 从源点流入 $i$ 出点的军队 + 区域原有的军队 - 从 $i$ 出点流出的军队。通过入点和出点之间的边容量，我们可以限制每个区域最终保留的军队数。

边的含义

1. 出点 $\to$ 入点：容量为 $a[i]$（区域原有的军队数）。
   这条边表示区域 $i$ 原有的军队必须经过它才能流动到其他地方，且不能超过原有数量。

2. 源点 $s$ $\to$ 出点：容量根据区域类型不同：

   • 如果是边界区域：容量为 $a[i]$（所有军队都可以调出）
   • 如果是内部区域：容量为 $a[i]-1$（必须保留一个军队）

   源点代表“可以重新分配的军队池”，这些军队可以流向任何需要的地方。

3. 入点 $i$ $\to$ 出点 $j+n$：如果区域 $i$ 和 $j$ 相邻且都是我方的，则添加容量为 $\infty$ 的边。
   这表示军队可以从区域 $i$ 移动到区域 $j$（通过 $i$ 的入点流入 $j$ 的出点）。

4. 出点 $\to$ 汇点 $t$：仅对边界区域添加，容量为 $mid$。
   这条边表示该边界区域最终需要保留 $mid$ 个军队。如果最大流能将这些边全部填满，就说明所有边界区域都能达到 $target$。

可行性判断

设边界区域的数量为 $m$，则所有边界区域需要的军队总数为 $m\times mid$。
计算从源点到汇点的最大流 $flow$，如果 $flow\ge m\times mid$，说明 $mid$ 可行。

为什么这个建模是正确的？

• 军队守恒：每个区域原有的军队通过“出点 $\to$ 入点”的边进入系统，最终通过“出点 $\to$ 汇点”的边离开系统（对边界区域）或留在系统中（对内部区域）。
• 移动约束：军队只能通过“入点 $\to$ 出点”的边在相邻区域间移动。
• 最低保留约束：内部区域的源点连接容量为 $a[i]-1$，确保了至少保留一个军队；边界区域的汇点连接容量为 $mid$，确保了最终数量。

代码实现

// Risk
// UVa ID: 12264
// Verdict: Accepted
// Submission Date: 2026-02-23
// UVa Run Time: 0.010s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

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

const int INF = 10000;
const int MAXN = 205;

class Dinic {
private:
    struct Edge {
        int to, cap, flow, rev;
    };
    vector<Edge> adj[MAXN];
    int level[MAXN], cur[MAXN];
public:
    void clear() {
        for (int i = 0; i < MAXN; i++) adj[i].clear();
    }
    void addEdge(int u, int v, int cap) {
        adj[u].push_back({v, cap, 0, (int)adj[v].size()});
        adj[v].push_back({u, 0, 0, (int)adj[u].size() - 1});
    }
    bool bfs(int s, int t) {
        memset(level, -1, sizeof(level));
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto &e : adj[u]) {
                if (level[e.to] < 0 && e.cap > e.flow) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] >= 0;
    }
    int dfs(int u, int t, int f) {
        if (u == t) return f;
        for (int &i = cur[u]; i < (int)adj[u].size(); i++) {
            Edge &e = adj[u][i];
            if (level[e.to] == level[u] + 1 && e.cap > e.flow) {
                int d = dfs(e.to, t, min(f, e.cap - e.flow));
                if (d > 0) {
                    e.flow += d;
                    adj[e.to][e.rev].flow -= d;
                    return d;
                }
            }
        }
        return 0;
    }
    int maxFlow(int s, int t) {
        int flow = 0;
        while (bfs(s, t)) {
            memset(cur, 0, sizeof(cur));
            int f;
            while ((f = dfs(s, t, INF)) > 0) flow += f;
        }
        return flow;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> army(n + 1);
        int totalArmy = 0;
        for (int i = 1; i <= n; i++) {
            cin >> army[i];
            totalArmy += army[i];
        }
        vector<bool> isBorder(n + 1, false);
        vector<vector<bool>> adj(n + 1, vector<bool>(n + 1, false));
        for (int i = 1; i <= n; i++) {
            string line;
            cin >> line;
            for (int j = 1; j <= n; j++) {
                if (line[j - 1] == 'Y') {
                    adj[i][j] = true;
                    if (army[i] > 0 && army[j] == 0) isBorder[i] = true;
                }
            }
        }
        int borderCount = 0;
        for (int i = 1; i <= n; i++)
            if (isBorder[i]) borderCount++;
        int left = 1, right = totalArmy, ans = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            Dinic dinic;
            int s = 0, t = 2 * n + 1;
            for (int i = 1; i <= n; i++) {
                if (army[i] == 0) continue;
                dinic.addEdge(i + n, i, army[i]);
                if (isBorder[i]) {
                    dinic.addEdge(s, i + n, army[i]);
                    dinic.addEdge(i + n, t, mid);
                } else {
                    dinic.addEdge(s, i + n, army[i] - 1);
                }
            }
            for (int i = 1; i <= n; i++) {
                if (army[i] == 0) continue;
                for (int j = 1; j <= n; j++) {
                    if (i != j && adj[i][j] && army[j] > 0)
                        dinic.addEdge(i, j + n, INF);
                }
            }
            int flow = dinic.maxFlow(s, t);
            if (flow >= borderCount * mid) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

复杂度分析

• 每次 $\text{maxFlow}$ 调用使用 $\text{Dinic}$ 算法，复杂度 $O(E\sqrt{V})$，其中 $V=2n+2$，$E=O(n^2)$。
• 二分查找次数为 $O(\log \sum a_i)$，总复杂度 $O(n^2\sqrt{n}\log \sum a_i)$，在 $n\le 100$ 时完全可行。