BZOJ 1475: 方格取数 – [网络流/最小割]

题目传送门(BZOJ)
>原文链接<

题解 :

​ 本题是网络流二十四题中的问题,考虑用网络流解决。

若要求选点 x ,则 x 周围的四个点都不能选,我们可以依据这个性质,把方格按 (i+j)\%2 黑白染色

对于黑色格子,我们从原点向它连一条流量为其权值的边,并且从它向周围四个格子连边,流量为 INF

对于白色格子,我们从它向汇点连一条流量为其权值的边。

之所以这样连边的原因是,我们要求一个方案不能有从 S \to x \to y \to T 的流,那么相当于割掉这些边。

为了让我们获得的权值尽可能的多,我们必须要求一个最小的割,根据 最小割 = 最大流 这个已经证明过的定理,我们可以对建出来的图求一个最大流,这样,答案就是 \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}a[i][j] – MaxFlow

代码 :

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 5000;
const int inf = 0x3f3f3f3f;
#define P(i,j) ((i-1)*m+j)
int head[N],to[N<<1],val[N<<1],nxt[N<<1];
int cnt = 1;
int dep[N<<1], sum;
int n, m, s, t;
void add_edge(int a, int b, int c) {
    to[++cnt] = b; nxt[cnt] = head[a]; head[a]  = cnt; val[cnt] = c;
    to[++cnt] = a; nxt[cnt] = head[b]; head[b]  = cnt; val[cnt] = 0;
}
queueq;
bool bfs() {
    memset(dep, 0, sizeof dep);
    while(!q.empty()) q.pop();
    q.push(s); dep[s] = 1;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u]; i; i = nxt[i]) if(!dep[to[i]]&&val[i]) {
            dep[to[i]] = dep[u]+1;
            if(to[i] == t) return 1;
            q.push(to[i]);
        }
    }
    return 0;
}
int dfs(int p,int mf) {
    int nf=0;
    if(p==t)return mf;
    for(int i=head[p];i;i=nxt[i]) {
        if(dep[to[i]]==dep[p]+1&&val[i]) {
            int tmp=dfs(to[i],min(mf-nf,val[i]));
            if(!tmp)dep[to[i]]=0;
            nf+=tmp;
            val[i]-=tmp;
            val[i^1]+=tmp;
            if(nf==mf)break;
        }
    }
    return nf;
}
void dinic() {
    int ans=0;
    while(bfs()) ans+=dfs(s,inf);
    printf("%d\n",sum-ans);
}
signed main() {
    scanf("%d",&n);
    m = n; s = n*m+1,t = n*m+2;
    for(int i = 1; i <= n; i ++ ) for(int j = 1, x; j <= m; j ++ ) {
        scanf("%d",&x);
        sum += x;
        if((i+j)&1) {
            add_edge(s, P(i, j), x);
            if(i>1) add_edge(P(i, j), P(i-1, j), inf);
            if(i1) add_edge(P(i, j), P(i, j-1), inf);
            if(j

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注