P4474 王者之剑

P4474 王者之剑

题目大意

n*m的带权网格，任意选择起点
开始时刻为0秒。以下操作，每秒按顺序执行

1. 在第i秒开始的时候，在方格（x,y）上，获得（x，y）的值
2. 在偶数秒，周围四格的值清零
3. 每秒可选择不动或走一格

求最大值

易证：选择获得某格上的值时，周围四格就不能获得了——二分图最大点权独立集

网格——奇偶分类

网络流跑最小割

My complete code: 

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
typedef long long LL;
const LL maxn=500000;
const LL inf=0x3f3f3f3f;
const LL dx[5]={0,-1,0,1,0};
const LL dy[5]={0,0,1,0,-1};
inline LL read(){
LL x=0,f=1; char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1; c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0'; c=getchar();
}return x*f;
}
struct node{
LL to,next,flow;
}dis[maxn];
LL num=-1,s,t,n,m,ans;
LL head[maxn],dep[maxn];
inline void Add(LL u,LL v,LL flow){
dis[++num]=(node){v,head[u],flow}; head[u]=num;
}
inline bool Bfs(){
memset(dep,0,sizeof(dep));
queue<LL> que;
que.push(s);
dep[s]=1;
while(que.size()){
LL u=que.front();
que.pop();
for(LL i=head[u];i!=-1;i=dis[i].next){
LL v=dis[i].to;
if(!dep[v]&&dis[i].flow){
dep[v]=dep[u]+1;
que.push(v);
}
}
}
return dep[t];
}
LL Dfs(LL u,LL flow){
if(u==t)
    return flow;
LL tmp=flow;
for(LL i=head[u];i!=-1;i=dis[i].next){
LL v=dis[i].to;
if(dep[v]==dep[u]+1&&dis[i].flow&&tmp){
LL now=Dfs(v,min(tmp,dis[i].flow));
if(now){
dis[i].flow-=now;
dis[i^1].flow+=now;
tmp-=now;
}else
    dep[v]=inf;
}
}
return flow-tmp;
}
inline LL Dinic(){
LL sum=0;
while(Bfs())
sum+=Dfs(s,inf);
return sum;
}
int main(){
n=read(); m=read();
s=0; t=n*m+1;
memset(head,-1,sizeof(head));
for(LL i=1;i<=n;++i)
    for(LL j=1;j<=m;++j){
    LL val=read();
    ans+=val;
    if((i+j)&1){
    Add(s,(i-1)*m+j,val);
    Add((i-1)*m+j,s,0);
}else{
        Add((i-1)*m+j,t,val);
        Add(t,(i-1)*m+j,0);
}
}for(LL i=1;i<=n;++i)
    for(LL j=1;j<=m;++j){
    if((i+j)&1){
    for(LL k=1;k<=4;++k){
    LL nx=i+dx[k],ny=j+dy[k];
    if(nx<1||nx>n||ny<1||ny>m)
        continue;
    Add((i-1)*m+j,(nx-1)*m+ny,inf);
    Add((nx-1)*m+ny,(i-1)*m+j,0);
}
}
}
ans-=Dinic();
printf("%lld",ans);
return 0;
}