P2774 方格取数问题

网络流最小割问题。

做了狼和羊后一脸蒙的被拉去做了这道题。开局继续蒙。

反正上课也没有听懂，只依稀记得一个什么奇数点放一边，偶数点放一边，建立二分图。
建完边之后，考虑继续连边，将所有可能产生影响的边连接在一起，这里只要把黑点连向白点就可以了。
因为最开始在构建这个网络流的时候，将$S$->黑->白->$T$，白连向黑你想干什么啊，河水逆流？

然后然后如果只看$j$的奇偶性的话肯定会出问题，因为你就相当于不会影响你上下的格子啦。

这道题暂时没有出任何问题！撒花～

#include <bits/stdc++.h>
#define ll int
#define INF 1000000000
#define maxn 43200
using namespace std;
ll m,n,a[110][110],cnt=1,hd[maxn];
ll s,t,l,r;
struct Node{
    ll nx,to,dis;
}e[maxn<<2];
ll ff[5][4]={{0,1},{0,-1},{1,0},{-1,0}};
ll d[maxn],ans,q[maxn];
ll sum;

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))
        f|c=='-',c=getchar();
    while(isdigit(c))
        x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

inline ll sm(ll u,ll v){
    return (u-1)*m+v;
}

inline void add(ll u,ll v,ll w){
    e[++cnt].to=v;
    e[cnt].nx=hd[u];
    e[cnt].dis=w;
    hd[u]=cnt;
}

inline ll bfs(){
    memset(d,0,sizeof(d));
    l=r=1;
    q[l]=s;
    d[s]=1;
    while(l<=r){
        ll u=q[l++];
        for(register int i=hd[u];i;i=e[i].nx){
            ll to=e[i].to;
            if(e[i].dis&&!d[to]){
                q[++r]=to;
                d[to]=d[u]+1;
            }
        }

    }
    return d[t];
}

inline ll dfs(ll u,ll limit){
    if(u==t)    return limit;
    ll flow=0;
    for(register int i=hd[u];i&&limit;i=e[i].nx){
        ll to=e[i].to;
        if(e[i].dis&&d[to]==d[u]+1){
            ll fj=dfs(to,min(limit,e[i].dis));
            e[i].dis-=fj;
            e[i^1].dis+=fj;
            flow+=fj;
            limit-=fj;
        }       
    }
    if(!flow)   d[u]=0;
    return flow;
}

int main(){
    n=read();m=read();
    s=n*m*2+1;t=n*m*2+2;
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            a[i][j]=read(),sum+=a[i][j];
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            if((i+j)&1){
                add(s,sm(i,j),a[i][j]);
                add(sm(i,j),s,0);
            }
            else{
                add(sm(i,j),t,a[i][j]);
                add(t,sm(i,j),0);
            }
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            if((i+j)&1){
                for(register int k=0;k<=3;++k){
                    ll dx=i+ff[k][0];
                    ll dy=j+ff[k][1];
                    if(dx>=1&&dx<=n&&dy>=1&&dy<=m)
                        add(sm(i,j),sm(dx,dy),INF),
                        add(sm(dx,dy),sm(i,j),0);
                }    
            }
            
    while(bfs())
        ans+=dfs(s,INF);
    printf("%d\n",sum-ans);
    return 0;
}