题目分析

本题要求我们通过最少的操作次数，将一个初始全为 $0$ 的 $n\times n$ 矩阵转换为目标符号矩阵。

操作定义

每次操作可以选择：

• 将某一整行的所有元素同时 $+1$ 或 $-1$
• 将某一整列的所有元素同时 $+1$ 或 $-1$

符号约束

目标矩阵中每个位置的符号有三种可能：

• + 表示该位置最终值 $>0$
• - 表示该位置最终值 $<0$
• 0 表示该位置最终值 $=0$

关键观察

设第 $i$ 行进行的净操作次数为 $R_i$（加为正，减为负），第 $j$ 列进行的净操作次数为 $C_j$，则矩阵中 $(i,j)$ 位置的最终值为：

$$A_{i,j}=R_i+C_j$$

因此，问题转化为：

• 寻找整数序列 $R_1,R_2,\dots ,R_n$ 和 $C_1,C_2,\dots ,C_n$
• 满足所有符号约束
• 最小化 ${\sum }_{i=1}^n|R_i|+{\sum }_{j=1}^n|C_j|$

---

解题思路

1. 约束条件的形式化

对于每个位置 $(i,j)$，根据目标符号有：

• 若为 + ：$R_i+C_j\ge 1$
• 若为 - ：$R_i+C_j\le -1$
• 若为 0 ：$R_i+C_j=0$

2. 变量代换与差分约束转化

这是本题最精妙的一步。我们引入新的变量表示，令：

• $X_i=R_i$，其中 $0\le i<n$
• $X_{n+j}=-C_j$，其中 $0\le j<n$

则原有的约束可以统一改写为：

对于 + 约束：
$$R_i+C_j\ge 1\Rightarrow R_i-(-C_j)\ge 1\Rightarrow X_{n+j}-X_i\le -1$$

对于 - 约束：
$$R_i+C_j\le -1\Rightarrow R_i-(-C_j)\le -1\Rightarrow X_i-X_{n+j}\le -1$$

对于 0 约束：
$$R_i+C_j=0\Rightarrow R_i-(-C_j)=0\Rightarrow \{\begin{array}{l}{X}_i-X_{n+j}\le 0\\ X_{n+j}-X_i\le 0\end{array}$$

所有约束都转化为了标准形式 $X_v-X_u\le w$，这正是差分约束系统的标准形式。

3. 图论建模

将每个变量 $X_k$ 视为图中的一个节点（共 $2n$ 个节点），对于每条约束 $X_v-X_u\le w$，添加一条从 $u$ 到 $v$ 的边，权值为 $w$。

具体建图规则：

• + ：添加边 $n+j\to i$，权值为 $-1$
• - ：添加边 $i\to n+j$，权值为 $-1$
• 0 ：添加边 $i\to n+j$ 和 $n+j\to i$，权值均为 $0$

4. 求解差分约束系统

使用 $\text{SPFA}$ 算法求解最短路：

• 将所有节点的初始距离设为 $0$，并全部加入队列
• 运行 $\text{SPFA}$，同时记录每个节点的入队次数
• 如果某个节点入队次数达到 $2n$ 次，说明图中存在负环，约束系统无解，输出 $-1$
• 否则，$dist$ 数组保存了一组可行解，即每个 $X_k$ 的一个可行取值

为什么初始距离设为 $0$ 且全部入队？

• 差分约束系统需要添加超级源点，但我们可以等价地将所有点初始距离设为 $0$ 并入队，效果相同且更简洁
• 这样可以找到一组使得所有变量尽可能接近 $0$ 的解

5. 还原变量并最小化操作次数

得到 $X$ 数组后，还原原始变量：

• $R_i=X_i$
• $C_j=-X_{n+j}$

由于差分约束系统只确定了变量之间的相对关系，我们可以给所有 $R_i$ 加上一个偏移量 $shift$：

• $R_i^{{}^{\prime }}=R_i+shift$
• 由于 $X_{n+j}=-C_j$ 也包含了相同的相对关系，对应地 $C_j^{{}^{\prime }}=C_j-shift$

操作总次数为：
$$\sum _{i=0}^{n-1}|R_i+shift|+\sum _{j=0}^{n-1}|C_j-shift|$$

代入 $C_j=-X_{n+j}$，得：
$$\sum _{i=0}^{n-1}|X_i+shift|+\sum _{j=0}^{n-1}|-X_{n+j}-shift|$$

我们只需在 $shift\in [-n,n]$ 范围内枚举，计算每种情况下的总操作次数，取最小值即可。

为什么枚举范围是 $[-n,n]$？

• 由于每个变量的值不会偏离 $0$ 太远（否则操作次数会很大），在 $n\le 100$ 时，$[-n,n]$ 的范围已经足够覆盖最优解

6. 时间复杂度分析

• 建图：$O(n^2)$
• $\text{SPFA}$ 算法：平均时间复杂度 $O(kE)$，其中 $E=O(n^2)$，$k$ 为常数
• 枚举平移量：$O(n^2)$

总体时间复杂度 $O(n^2)$，在 $n\le 100$ 时可以在毫秒级完成所有测试用例。

---

参考代码

// Sign of a Matrix
// UVa ID: 11671
// Verdict: Accepted
// Submission Date: 2026-04-12
// UVa Run Time: 0.010s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

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

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

struct Edge {
    int to, weight;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, caseNum = 0;
    while (cin >> n && n != -1) {
        vector<string> grid(n);
        for (int i = 0; i < n; ++i) cin >> grid[i];
        
        int total = 2 * n;
        vector<vector<Edge>> adj(total);
        
        // 根据符号建图
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) {
                int u = i;          // R[i]
                int v = n + j;      // -C[j]
                if (grid[i][j] == '+') 
                    adj[v].push_back({u, -1});  // -C[j] - R[i] <= -1
                else if (grid[i][j] == '-') 
                    adj[u].push_back({v, -1});  // R[i] - (-C[j]) <= -1
                else {  // '0'
                    adj[u].push_back({v, 0});   // R[i] - (-C[j]) <= 0
                    adj[v].push_back({u, 0});   // -C[j] - R[i] <= 0
                }
            }
        
        // SPFA 求最短路并检测负环
        vector<int> dist(total, 0);  // 所有点初始距离为 0
        vector<int> cnt(total, 0);
        vector<bool> inQueue(total, true);
        queue<int> q;
        
        for (int i = 0; i < total; ++i) q.push(i);
        
        bool hasNegCycle = false;
        while (!q.empty() && !hasNegCycle) {
            int u = q.front();
            q.pop();
            inQueue[u] = false;
            
            for (const Edge& e : adj[u]) {
                int v = e.to;
                int w = e.weight;
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= total) {
                        hasNegCycle = true;
                        break;
                    }
                    if (!inQueue[v]) {
                        q.push(v);
                        inQueue[v] = true;
                    }
                }
            }
        }
        
        cout << "Case " << ++caseNum << ": ";
        if (hasNegCycle) {
            cout << -1 << "\n";
            continue;
        }
        
        // 计算最小操作次数：枚举平移量
        int ans = INF;
        for (int shift = -n; shift <= n; ++shift) {
            int sum = 0;
            for (int i = 0; i < n; ++i) 
                sum += abs(dist[i] + shift);           // R[i]
            for (int j = 0; j < n; ++j) 
                sum += abs(-dist[n + j] - shift);      // C[j] = -(-C[j]) 的相反数
            ans = min(ans, sum);
        }
        
        cout << ans << "\n";
    }
    return 0;
}

---

总结

本题是一道经典的差分约束系统应用题，核心难点在于：

1. 问题转化：将矩阵操作转化为行变量和列变量的线性组合
2. 变量代换：通过令 $X_{n+j}=-C_j$，将所有约束统一为 $X_v-X_u\le w$ 的形式
3. 图论建模：将差分约束转化为有向图中的边，使用 $\text{SPFA}$ 算法求解
4. 最优化处理：通过枚举平移量找到使操作次数最小的解

掌握这种将代数约束转化为图论模型的方法，对于解决许多组合优化问题都有很大帮助。差分约束系统不仅适用于本题，在求解诸如区间约束、任务调度等问题时也有广泛应用。