题解 P2774 【方格取数问题】

· · 题解

题目名称：方格取数问题

来源：网络流24题

链接

博客链接

题目链接

提示

注意试题来源！

题解

这道题要我们求的是从方格中取得的数最大的和。

不难发现，直接求不太好求。

因为我们取这个格子里的数的条件，不是取了某个格子里的数，而是未取某些格子里的数。如果我们直接用最大流来写的话，不太好连边。

著名的数学家（神犇）Isaac Newton（虽然说是数学家，但是无意间把OIer往死里坑）曾经说过“正难则反”。

那么我换一下思路，我可以将取得的最大和变为总和-最小代价，这里的代价是指，如果不取某些格子上的数，可以使取的方案合法，这样的格子上的数的总和。

我们将格子进行黑白染色，保证相邻颜色不同，并按顺序给每个格子标上编号，拿样例说话。

如图，蓝色即是黑色，红色即是白色，方格内是权值。

开始考虑建图：（注意：这里连边都是在格子的编号之间连边）

  1. 将源点向所有染黑色格子连边。容量为其权值。
  2. 将所有染黑色格子向汇点连边。容量为其权值。
  3. 将所有互相冲突的格子（上下左右四个格子）连边，方向为从黑格子向白格子，容量为\infty。

又拿样例说话

不难发现，互相冲突的两个格子必须有一个不被选，在图上就表现为至少有一个到源点或汇点的边要割掉。（因为不可能割中间容量为\infty的边）

所以答案就是所有格子上数的总和减去最小割。

跑一遍Dinic就可以了。

//C++
#include<bits/locale_facets.h>
#include<bitset>
#include<limits.h>
#include<memory.h>
#include<stdio.h>
#include<queue>
#define downt(i,n) for(int i=n;i;i=back[i])
#define forto(name,i,d,u) for(name i=d;i<=u;i++)
#define foruntil(name,i,d,u) for(name i=d;i<u;i++)
const short nm=101;
inline void output(long long o); 
inline long long input();
short number[nm][nm];
std::bitset<nm>BW[nm];
template<int nn,int mm,typename name>struct network{
#define nnn (nn+3)
#define mmmm (mm<<2)+2
    int s,t,tot,nnnn,last[nnn],level[nnn],to[mmmm],arc[mmmm],back[mmmm];
    name c[mmmm];
    std::queue<int>q;
    network(){nnnn=nnn<<2,INIT();}
#undef nnn
#undef mmmm
    void INIT(){tot=1,memset(last,0,nnnn);}
    void add(int f,int t,name cap){to[++tot]=t,c[tot]=cap,back[tot]=last[f],last[f]=tot;}
    void insert(int f,int t,name cap){
        if(cap){
            if(cap<0)std::swap(f,t),cap=-cap;
            add(f,t,cap),add(t,f,0);
        }
    }bool climb(){
        memset(level,0,nnnn),q.push(s),level[s]=0;
        for(int p,too;!q.empty();q.pop()){
            p=q.front(),level[p]++;
            downt(i,last[p])
            if(c[i]&&!level[too=to[i]])level[too]=level[p],q.push(too);
        }return level[t];
    }name augment(int p,name m){
        if(p==t)return m;
        name sum=0,flow;
        int d=level[p]+1;
        for(;arc[p];arc[p]=back[arc[p]])
        if(level[to[arc[p]]]==d&&c[arc[p]]){
            sum+=(flow=augment(to[arc[p]],std::min(c[arc[p]],(name)(m-sum)))),c[arc[p]]-=flow,c[arc[p]^1]+=flow;
            if(sum==m)return m;
        }return sum;
    }name Dinic(name inf){
        name maximum=0;
        while(climb()){
            foruntil(int,i,s,t)arc[i]=last[i];
            maximum+=augment(s,inf);
        }return maximum;
    }
};network<10000,50000,int>check;
int main(){
    short m=input(),n=input(),e;
    int sum=0,inf=0x3f3f3f;
    check.s=0,check.t=m*n+1,BW[1][1]=true,number[1][1]=1;
    forto(short,i,2,m)BW[i][1]=!BW[i-1][1],number[i][1]=(i-1)*n+1;
    forto(short,i,1,m)
    forto(short,j,2,n)BW[i][j]=!BW[i][j-1],number[i][j]=(i-1)*n+j;
    forto(short,i,1,m)
    forto(short,j,1,n){
        sum+=(e=input());
        if(BW[i][j]){
            check.insert(0,number[i][j],e);
            if(i>1)check.insert(number[i][j],number[i-1][j],inf);
            if(j>1)check.insert(number[i][j],number[i][j-1],inf);
            if(i<m)check.insert(number[i][j],number[i+1][j],inf);
            if(j<n)check.insert(number[i][j],number[i][j+1],inf);
        }else check.insert(number[i][j],check.t,e);
    }output(sum-check.Dinic(INT_MAX));
    return 0;
}inline void output(long long o){
    if(o<0)putchar('-'),o=-o;
    if(o>=10)output(o/10);
    putchar(o%10^'0');
}inline long long input(){
    bool minus=false;
    char now=getchar();
    long long i=0;
    for(;!isdigit(now);now=getchar())
    if(now=='-')minus=!minus;
    for(;isdigit(now);now=getchar())i=(i<<3)+(i<<1)+(now^'0');
    return minus?-i:i;
}

题集