题解：P8619 [蓝桥杯 2014 国 B] 殖民地

William_dongdong · 2026-10-18 20:56:30 · 题解

题目大意

在一个 M\times N 的表格中，每个格子有一个整数 A_{i,j}。我们可以选择一些格子并建立围栏将其与其他格子隔开。建围栏需要一定的代价：如果相邻两个格子选择状态不同（一个被选，一个没被选），则需要建立它们之间的围栏，如果边界格子被选，则需要建立边界围栏。

思路

这是一个最小割问题。我们可以把每个格子看作二分图中的一个点：

• 格子与源点 S 连通，表示选择该格子。
• 格子与汇点 T 连通，表示不选择该格子。

如果选择了正收益的格子，我们会得到收益；如果没有选择，这部分收益就损失了。同理，如果选择了负收益的格子，就要付出代价。因此，我们可以先假设所有正收益的格子都被选择，把这些收益加起来得到 tot。但相邻格子状态不同时要付出围栏代价，我们可以通过最小割来求出最少需要放弃多少收益或支付多少代价，所以最终答案即为 tot- 最小割（我们知道最小割 = 最大流，所以最终答案为 tot- 最大流），但我们怎么建图呢？

建图

格子的收益与代价（矩阵 A）

• 如果 A_{i,j}>0，连边 S\rightarrow (i,j)，容量为 A_{i,j}，若最终不选它（割断此边），相当于损失了 A_{i,j} 的流量。

• 如果 A_{i,j}<0，连边 (i,j)\rightarrow T，容量为 -A_{i,j}，若最终选它（割断此边），相当于获得了 -A_{i,j} 的流量。

内部围栏（矩阵 B 和 C）

• 如果相邻两个格子状态不同（一个选一个不选），必须建围栏。

• 连双向边：上下相邻连 (i−1,j) 和 (i,j)，容量为 B_{i,j}，左右相邻连 (i,j−1) 和 (i,j)，容量为 C_{i,j}。

边界围栏（矩阵 B 和 C 的边缘）

• 如果边界格子被选中，必然要建立边界围栏。

• 连边 (i,j)\rightarrow T，容量为对应的边界围栏代价。

代码

:::info[ACcode]

#include <algorithm>
#include <array>
#include <atomic>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <condition_variable>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <future>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <mutex>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <ratio>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <system_error>
#include <thread>
#include <tuple>
#include <type_traits>
#include <typeinfo>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
#define double long long
#define def signed
#define CE constexpr
#define XH for
#define AKIOI 1
#define AFO 0
#define static inline
#define LLONG_MIN LLONG_MAX
#define qread std

CE double aaa=4e4+10;CE double aab=2*1.2e5+10;CE double aac=LLONG_MIN>>AKIOI;
double aad,aae,aaf,aag;
static double aah(){
    double aai=AFO,aaj=AKIOI;char aak=qread::getchar();while(aak<'0'||aak>'9'){if(aak=='-')aaj=-AKIOI;aak=qread::getchar();
    }while(aak>='0'&&aak<='9'){aai=aai*10+aak-'0';aak=qread::getchar();}return aai*aaj;}
typedef struct node{
    double aal,aam,aan;node()=default;node(double aao,double aap,double aaq):aal(aao),aam(aap),aan(aaq){}
}edge;
qread::vector<edge>aar[aaa];double aas[aaa];double aat[aaa];double aau[aaa];double aav[aaa];double aaw[aaa];qread::stack<double>aap[aaa];double aax;
static void aay(double aaz,double aba,double aaq){
    aar[aaz].emplace_back(aba,aaq,aar[aba].size());aar[aba].emplace_back(aaz,AFO,aar[aaz].size()-AKIOI);
}
static double abb(double aaz){
    bool abc=(aaz==aaf);XH(auto &abd:aar[aaz]){
        double &aba=abd.aal;double &aam=abd.aam;double &aan=abd.aan;if(!aam||(!abc&&aau[aaz]!=aau[aba]+AKIOI)||aau[aba]==aac)continue;
        double abe=abc?aam:qread::min(aam,aav[aaz]);if(aba!=aaf&&aba!=aag&&!aav[aba]){
            aap[aau[aba]].push(aba);aax=qread::max(aax,aau[aba]);
        }aav[aaz]-=abe;aav[aba]+=abe;aam-=abe;aar[aba][aan].aam+=abe;if(!aav[aaz])return AFO;}
    return AKIOI;}
static void abf(double aaz,double aad){
    aau[aaz]=aac;XH(auto &abd:aar[aaz]){
        if(abd.aam){aau[aaz]=qread::min(aau[aaz],aau[abd.aal]);}
    }++aau[aaz];if(aau[aaz]<aad){aap[aau[aaz]].push(aaz);aax=qread::max(aax,aau[aaz]);++aaw[aau[aaz]];}
}
static bool abg(double aad){
    XH(double abh=AKIOI;abh<=aad+9;++abh)aau[abh]=aac;qread::queue<double>abi;abi.push(aag);aau[aag]=AFO;
    while(!abi.empty()){double aaz=abi.front();abi.pop();XH(auto &abd:aar[aaz]){
            double &aba=abd.aal;double &aan=abd.aan;if(aar[aba][aan].aam&&aau[aba]>aau[aaz]+AKIOI){
                aau[aba]=aau[aaz]+AKIOI;abi.push(aba);}
                }}return aau[aaf]!=aac;}static double abj(){while(aax>-AKIOI&&aap[aax].empty())--aax;return aax==-AKIOI?AFO:aap[aax].top();}
            static double abk(double aad){if(!abg(aad))return AFO;
XH(double abh=AKIOI;abh<=aad+9;++abh)aaw[abh]=AFO;
XH(double abh=AKIOI;abh<=aad;++abh){if(aau[abh]!=aac){
    ++aaw[aau[abh]];}}aau[aaf]=aad;abb(aaf);double aaz;while((aaz=abj())){aap[aax].pop();
    if(abb(aaz)){if(!--aaw[aau[aaz]]){XH(double abh=AKIOI;abh<=aad;++abh){if(abh!=aaf&&aau[abh]>aau[aaz]&&aau[abh]<aad+AKIOI){aau[abh]=aad+AKIOI;}}
    }abf(aaz,aad);}}return aav[aag];}static void abl(){aae=aah();aad=aah();aaf=AFO;aag=aad*aae+AKIOI;double abm=AFO;XH(double abh=AKIOI;abh<=aae;++abh){
        XH(double abn=AKIOI;abn<=aad;++abn){double aao=aah();double abo=(abh-AKIOI)*aad+abn;if(aao>AFO){aay(aaf,abo,aao);abm+=aao;
        }else{aay(abo,aag,-aao);}}}XH(double abh=AKIOI;abh<=aae+AKIOI;++abh){XH(double abn=AKIOI;abn<=aad;++abn){
            double aap=aah();if(abh==AKIOI){aay(abn,aag,aap);}else if(abh==aae+AKIOI){aay((aae-AKIOI)*aad+abn,aag,aap);
            }else{double aaz=(abh-2)*aad+abn;double aba=(abh-AKIOI)*aad+abn;aay(aaz,aba,aap);aay(aba,aaz,aap);}}
            }XH(double abh=AKIOI;abh<=aae;++abh){XH(double abn=AKIOI;abn<=aad+AKIOI;++abn){double aaq=aah();if(abn==AKIOI){aay((abh-AKIOI)*aad+AKIOI,aag,aaq);
            }else if(abn==aad+AKIOI){aay((abh-AKIOI)*aad+aad,aag,aaq);
            }else{double aaz=(abh-AKIOI)*aad+(abn-AKIOI);double aba=(abh-AKIOI)*aad+abn;aay(aaz,aba,aaq);aay(aba,aaz,aaq);}}
        }
        qread::printf("%lld\n",abm-abk(aag));
    }
def main(){abl();return AFO;}

:::