zcmimi's blog
avatar
zc
2020-06-15 21:47:00
  • 本文总阅读量
查看原题

点击跳转

首先奇偶黑白染色,源点连黑点,白点连汇点,边权为点权

接着所有黑点向相邻的白点连边,边权为\infty

答案就是 点权和-最小割

#include<bits/stdc++.h>
#define fur(i,x,y) for(int i=x;i<=y;++i)
int rd(){int x=0;char c;bool f=0;for(c=getchar();c<'0'||'9'<c;c=getchar())f^=c=='-';for(x=c-48,c=getchar();'0'<=c&&c<='9';x=x*10+c-48,c=getchar());return f?-x:x;}
const int N=11111,inf=-1u>>1;
#define id(i,j) (i-1)*m+j
int n,m,ans,st=N-2,ed=N-1,cnt=1,head[N];
struct edge{int to,nxt,w;}e[N*8];
void add(int x,int y,int w){
    e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;e[cnt].w=w;
    e[++cnt].to=x;e[cnt].nxt=head[y];head[y]=cnt;e[cnt].w=0;
}
int q[N],d[N];
bool bfs(){
    int h=0,t=1,x;
    memset(d,0,sizeof d);
    d[q[0]=st]=1;
    while(h<t){
        x=q[h++];if(x==ed)return 1;
        for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
            if(e[i].w&&!d[to])d[to]=d[x]+1,q[t++]=to;
    }
    return 0;
}
int min(int x,int y){return x<y?x:y;}
int dfs(int x,int mf){
    if(x==ed)return mf;
    int us=0,w;
    for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
        if(d[to]==d[x]+1&&e[i].w){
            w=dfs(to,min(mf-us,e[i].w));
            e[i].w-=w,e[i^1].w+=w;
            us+=w;if(us==mf)return mf;
        }
    if(!us)d[x]=-1;
    return us;
}
int main(){
    n=rd(),m=rd();
    int w;
    fur(i,1,n)fur(j,1,m){
        w=rd(),ans+=w;
        if((i+j)&1){
            add(st,id(i,j),w);
            if(i>1)add(id(i,j),id(i-1,j),inf);
            if(i<n)add(id(i,j),id(i+1,j),inf);
            if(j>1)add(id(i,j),id(i,j-1),inf);
            if(j<m)add(id(i,j),id(i,j+1),inf);
        }
        else add(id(i,j),ed,w);
    }
    while(bfs())ans-=dfs(st,inf);
    printf("%d\n",ans);
}
LG 4474 王者之剑
comment评论
Search
search