用图论解决连续宫格可以改变值的最小花费问题

用图论解决连续宫格可以改变值的最小花费问题

在网格路径规划、图像处理的区域填充、游戏地图的资源分配等场景中，经常需要处理一类优化问题：给定一个二维宫格，每个单元格有初始值，修改单元格的值需要一定花费，要求找到一片连续的连通区域，将该区域内所有单元格修改为同一目标值，使得总花费最小。这类问题可通过图论模型转化为经典的图论问题求解，本文将详细介绍具体方案。

一、问题定义与图论建模基础

问题形式化描述

设存在 $m\times n$ 的二维宫格 G={ci,j∣1≤i≤m,1≤j≤n}G = \{c_{i,j} \mid 1 \leq i \leq m, 1 \leq j \leq n\}G={ci,j​∣1≤i≤m,1≤j≤n}，其中每个单元格 $c_{i,j}$ 的初始值为 $v_{i,j}\in \mathbb{V}$（$\mathbb{V}$ 为所有可能取值的集合）。定义：

• 代价函数 $cost(c_{i,j},t)$：表示将单元格 $c_{i,j}$ 的值从初始值 $v_{i,j}$ 修改为目标值 $t$ 的花费（$t\in \mathbb{V}$）
• 连续区域（连通区域）：由4-邻接（上下左右相邻）的单元格组成的非空集合，即对于区域内任意两个单元格，存在一条通过相邻单元格的路径连接它们

问题目标：找到目标值 $t\in \mathbb{V}$ 和连通区域 $S\subseteq G$，使得总修改花费最小：
$$\underset{t\in \mathbb{V},S\subseteq G}{\min }\left(\sum _{c_{i,j}\in S}cost(c_{i,j},t)\right)$$
其中 $S$ 必须满足 4-连通性约束。

核心难点与图论转化思路

该问题的核心挑战在于连通性约束与多目标优化的耦合。直接枚举所有可能的连通区域和目标值组合，时间复杂度为 $O(|\mathbb{V}|\cdot 2^{mn})$，在宫格规模较大时完全不可行。

图论建模的关键思路是：

1. 将每个单元格映射为图中的节点
2. 用边表示单元格间的邻接关系，通过边的权重控制连通性
3. 将修改代价转化为节点或边的权重，将原问题转化为最小生成树、最小割等可高效求解的图论问题

二、基于最小生成树（MST）的解决方案

当问题要求覆盖全宫格（即 $S=G$）时，可通过最小生成树模型求解。此时只需确定目标值 $t$，使全宫格修改为 $t$ 的总花费最小，同时保证连通性（全宫格天然连通）。

模型构建

1. 节点定义：每个单元格 $c_{i,j}$ 对应图中的节点 $u_{i,j}$，节点权重为 $w_{i,j}=cost(c_{i,j},t)$（固定目标值 $t$ 时的修改代价）
2. 边定义：对于4-邻接的单元格 $c_{i,j}$ 和 $c_{k,l}$，在对应节点 $u_{i,j}$ 与 $u_{k,l}$ 间添加无向边，边权重为 $0$（表示维持连通性无需额外代价）
3. 目标转化：全宫格的总修改代价等于所有节点权重之和，而最小生成树恰好包含所有节点且边权重总和最小（此处为0），因此总代价为：
   $$Total(t)=\sum _{i=1}^m\sum _{j=1}^n{w}_{i,j}+\sum _{e\in MST}weight(e)=\sum _{i=1}^m\sum _{j=1}^{n}cost(c_{i,j},t)$$

算法流程

1. 遍历所有可能的目标值 $t\in \mathbb{V}$
2. 对每个 $t$，计算所有节点的权重 $w_{i,j}=cost(c_{i,j},t)$
3. 构建包含所有节点和邻接边的图，用 Kruskal 或 Prim 算法求最小生成树
4. 计算该 $t$ 对应的总代价 $Total(t)$，取所有 $t$ 中的最小值

代码实现（Prim算法）

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

// 计算固定目标值t时的全宫格最小代价
int computeTotalCost(const vector<vector<int>>& cost, int m, int n) {
    int total = 0;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            total += cost[i][j];
    return total;
}

// Prim算法验证连通性（全宫格必连通，此处用于演示）
bool isConnected(const vector<vector<int>>& grid, int m, int n) {
    if (m == 0 || n == 0) return true;
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    queue<pair<int, int>> q;
    q.push({0, 0});
    visited[0][0] = true;
    int count = 1;
    vector<pair<int, int>> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    
    while (!q.empty()) {
        auto [i, j] = q.front(); q.pop();
        for (auto [di, dj] : dirs) {
            int ni = i + di, nj = j + dj;
            if (ni >= 0 && ni < m && nj >=0 && nj < n && !visited[ni][nj]) {
                visited[ni][nj] = true;
                count++;
                q.push({ni, nj});
            }
        }
    }
    return count == m * n;
}

// 求解全宫格最小修改代价
int solveFullGrid(const vector<vector<vector<int>>>& cost_matrix, int m, int n, int num_values) {
    int min_total = INT_MAX;
    for (int t = 0; t < num_values; ++t) {
        vector<vector<int>> cost(m, vector<int>(n));
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                cost[i][j] = cost_matrix[i][j][t];
        
        if (isConnected(cost, m, n)) {
            int total = computeTotalCost(cost, m, n);
            if (total < min_total)
                min_total = total;
        }
    }
    return min_total;
}

int main() {
    // 示例：3x3宫格，目标值可选0,1,2
    int m = 3, n = 3;
    vector<vector<vector<int>>> cost_matrix = {
        {{1, 3, 2}, {4, 1, 5}, {2, 6, 1}},
        {{3, 2, 4}, {1, 2, 3}, {5, 1, 2}},
        {{2, 5, 3}, {6, 2, 1}, {3, 4, 2}}
    };
    int num_values = 3;
    
    cout << "全宫格最小修改代价: " << solveFullGrid(cost_matrix, m, n, num_values) << endl;
    return 0;
}

复杂度分析

• 时间复杂度：对于每个目标值 $t$，Prim 算法的时间复杂度为 $O((mn{)}^2)$（邻接矩阵实现），总复杂度为 $O(|\mathbb{V}|\cdot (mn{)}^2)$
• 空间复杂度：$O(mn)$ 用于存储节点权重和访问标记

三、基于最小割（Min-Cut）的解决方案

当问题允许选择任意连通子区域（$S\subset G$）时，需采用最小割模型。通过构建带源汇的流网络，将连通性约束转化为割集的容量约束。

模型构建

1. 网络结构：

   • 源点 $s$ 和汇点 $t$（虚拟节点）
   • 每个单元格 $c_{i,j}$ 对应节点 $v_{i,j}$
   • 源点 $s$ 到 $v_{i,j}$ 的边容量为 $cost(c_{i,j},t)$（表示不选择该单元格的代价）
   • $v_{i,j}$ 到汇点 $t$ 的边容量为 $0$（表示选择该单元格的代价）
   • 4-邻接节点 $v_{i,j}$ 与 $v_{k,l}$ 间添加双向边，容量为 $P$（$P$ 为足够大的惩罚值，确保非连通区域的割集容量更大）

2. 最小割的意义：

   • 割集 $(A,B)$ 将节点分为 $A$（含 $s$）和 $B$（含 $t$）两部分，A∖{s}A \setminus \{s\}A∖{s} 即为选中的连通区域
   • 割集容量为：
     $$C(A,B)=\sum _{v_{i,j}\in B}cost(c_{i,j},t)+\sum _{\begin{array}{c}{v}_{i,j}\in A,v_{k,l}\in B\\ (v_{i,j},v_{k,l})\in E\end{array}}P$$
     当 $P$ 足够大时（如 $P>{\sum }_{i,j}cost(c_{i,j},t)$），第二项仅在 A∖{s}A \setminus \{s\}A∖{s} 非连通时非零，因此最小割对应连通区域的最小代价。

算法流程

1. 遍历所有目标值 $t\in \mathbb{V}$
2. 对每个 $t$，按上述规则构建流网络
3. 用 Dinic 算法计算 $s$ 到 $t$ 的最小割容量（等于最大流）
4. 最小割容量即为该 $t$ 对应的最小子区域代价，取所有 $t$ 中的最小值

代码实现（Dinic算法）

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

struct Edge {
    int to, rev;
    long long cap;
    Edge(int t, int r, long long c) : to(t), rev(r), cap(c) {}
};

class Dinic {
public:
    vector<vector<Edge>> graph;
    vector<int> level, ptr;
    Dinic(int n) : graph(n), level(n), ptr(n) {}
    
    void addEdge(int from, int to, long long cap) {
        graph[from].emplace_back(to, graph[to].size(), cap);
        graph[to].emplace_back(from, graph[from].size()-1, 0);
    }
    
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& e : graph[u]) {
                if (e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                    if (e.to == t) return true;
                }
            }
        }
        return false;
    }
    
    long long dfs(int u, int t, long long flow) {
        if (u == t) return flow;
        for (int& i = ptr[u]; i < graph[u].size(); ++i) {
            Edge& e = graph[u][i];
            if (e.cap > 0 && level[e.to] == level[u] + 1) {
                long long pushed = dfs(e.to, t, min(flow, e.cap));
                if (pushed > 0) {
                    e.cap -= pushed;
                    graph[e.to][e.rev].cap += pushed;
                    return pushed;
                }
            }
        }
        return 0;
    }
    
    long long maxFlow(int s, int t) {
        long long total = 0;
        while (bfs(s, t)) {
            fill(ptr.begin(), ptr.end(), 0);
            while (long long pushed = dfs(s, t, LLONG_MAX))
                total += pushed;
        }
        return total;
    }
};

// 计算目标值t对应的最小子区域代价
long long minSubsetCost(const vector<vector<int>>& cost, int m, int n, int t) {
    const long long P = 1e18;  // 惩罚值（需大于最大可能总代价）
    int nodes = m * n;
    int s = nodes, t_sink = nodes + 1;
    Dinic dinic(nodes + 2);
    
    // 添加源汇与单元格的边
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int idx = i * n + j;
            dinic.addEdge(s, idx, cost[i][j]);       // 不选择的代价
            dinic.addEdge(idx, t_sink, 0);           // 选择的代价
        }
    }
    
    // 添加相邻单元格的惩罚边
    vector<pair<int, int>> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int idx = i * n + j;
            for (auto [di, dj] : dirs) {
                int ni = i + di, nj = j + dj;
                if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
                    int nidx = ni * n + nj;
                    dinic.addEdge(idx, nidx, P);
                    dinic.addEdge(nidx, idx, P);
                }
            }
        }
    }
    
    return dinic.maxFlow(s, t_sink);
}

// 求解最小子区域总代价
long long solveSubset(const vector<vector<vector<int>>>& cost_matrix, int m, int n, int num_values) {
    long long min_total = LLONG_MAX;
    for (int t = 0; t < num_values; ++t) {
        vector<vector<int>> cost(m, vector<int>(n));
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                cost[i][j] = cost_matrix[i][j][t];
        
        long long current = minSubsetCost(cost, m, n, t);
        if (current < min_total)
            min_total = current;
    }
    return min_total;
}

int main() {
    // 示例：2x2宫格
    int m = 2, n = 2;
    vector<vector<vector<int>>> cost_matrix = {
        {{2, 5, 3}, {4, 1, 6}},
        {{3, 2, 5}, {1, 4, 2}}
    };
    int num_values = 3;
    
    cout << "子区域最小修改代价: " << solveSubset(cost_matrix, m, n, num_values) << endl;
    return 0;
}

复杂度分析

• 时间复杂度：Dinic 算法在该网络中的时间复杂度为 $O(E\sqrt{E})$，其中 $E\approx 5mn$，总复杂度为 $O(|\mathbb{V}|\cdot mn\sqrt{mn})$
• 空间复杂度：$O(mn)$ 用于存储流网络结构

四、方案对比与优化策略

两种方案的适用场景

实用优化技巧

1. 代价矩阵预处理：

   • 移除冗余目标值（如某目标值的所有代价均大于其他值）
   • 合并等价单元格（初始值和代价矩阵完全相同的单元格）

2. 网络优化：

   • 对最小割模型，采用稀疏图存储减少内存占用
   • 动态调整惩罚值 $P$，避免数值溢出或精度问题

3. 并行计算：

   • 对不同目标值 $t$ 的计算可并行处理，提高效率

五、总结

连续宫格的最小修改代价问题可通过图论模型高效求解：

• 全宫格场景适合用最小生成树，利用节点权重直接计算总代价
• 子区域场景需用最小割模型，通过流网络的割集约束保证连通性

实际应用中，需根据是否允许选择子区域、宫格规模和目标值数量选择合适方案，并通过预处理和并行计算进一步优化性能。