学步园

没加当前弧优化 56ms

#include<bits/stdc++.h>
#define inf 1000000000
using namespace std;
const int xx[4]={-1,1,0,0},yy[4]={0,0,-1,1};
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct edge{
	int to,next,v;
}e[100001];
int n,m,cnt=1,T,ans,a[101][101],id[101][101],head[10001],h[10001],q[10001];
inline void ins(int u,int v,int w){
	e[++cnt]=(edge){v,head[u],w};head[u]=cnt;
	e[++cnt]=(edge){u,head[v],0};head[v]=cnt;
}
inline bool bfs(){  
    int t=0,w=0,now,q[20001];  
    memset(h,-1,sizeof(h));  
    h[0]=q[0]=0;  
    while(t<=w){  
        now=q[t++];  
        for(int i=head[now];i;i=e[i].next){  
            if(e[i].v&&h[e[i].to]==-1){  
                h[e[i].to]=h[now]+1;  
                q[++w]=e[i].to;  
            }  
        }  
    }  
    if(h[T]==-1)return 0;  
    else return 1;  
}  
inline int dfs(int x,int f){  
    if(x==T)return f;  
    int used=0,rest;  
    for(int i=head[x];i;i=e[i].next){  
        if(e[i].v&&h[e[i].to]==h[x]+1){  
            rest=f-used;  
            rest=dfs(e[i].to,min(e[i].v,rest));  
            e[i].v-=rest;  
            e[i^1].v+=rest;  
            used+=rest;  
            if(used==f)return f;  
        }  
    }  
    if(!used)h[x]=-1;  
    return used;  
}  
inline void dinic(){
	while(bfs())ans-=dfs(0,inf);
}
int main(){
	n=read();m=read();T=n*m+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			a[i][j]=read(),ans+=a[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if((i+j)&1){
				ins(0,(i-1)*m+j,a[i][j]);
				for(int k=0;k<4;k++){
					int x=i+xx[k],y=j+yy[k];
					if(x<=0||y<=0||x>n||y>m)continue;
					ins((i-1)*m+j,(x-1)*m+y,inf);
				}
			}
			else ins((i-1)*m+j,T,a[i][j]);
		}
	dinic();
	printf("%d",ans);
	return 0;
}

加了当前弧优化 56ms

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<vector>
#include<algorithm>
#define inf 1000000000
#define ll long long 
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,T,ans,cnt=1;
int a[105][105],id[105][105];
int last[10005],cur[10005],h[10005],q[10005];
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
struct data{int to,next,v;}e[100005];
void insert(int u,int v,int w)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;
}
bool bfs()
{
	for(int i=1;i<=T;i++)h[i]=-1;
	int head=0,tail=1;
	q[0]=h[0]=0;
	while(head!=tail)
	{
		int now=q[head];head++;
		for(int i=last[now];i;i=e[i].next)
			if(h[e[i].to]==-1&&e[i].v)
			{
				h[e[i].to]=h[now]+1;
				q[tail++]=e[i].to;
			}
	}
    return h[T]!=-1;
}
int dfs(int x,int f)
{
	if(x==T)return f;
	int w,used=0;
	for(int i=cur[x];i;i=e[i].next)
		if(h[e[i].to]==h[x]+1)
		{
			w=f-used;
			w=dfs(e[i].to,min(w,e[i].v));
			e[i].v-=w;if(e[i].v)cur[x]=i;e[i^1].v+=w;
			used+=w;if(f==used)return f;
		}
	if(!used)h[x]=-1;
	return used;
}
void dinic()
{
	while(bfs()){for(int i=0;i<=T;i++)cur[i]=last[i];ans-=dfs(0,inf);}
}
void build()
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			id[i][j]=(i-1)*m+j;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if((i+j)&1)
			{
				insert(0,id[i][j],a[i][j]);
				for(int k=0;k<4;k++)
				{
					int nowx=i+xx[k],nowy=j+yy[k];
					if(nowx<1||nowy<1||nowx>n||nowy>m)continue;
					insert(id[i][j],id[nowx][nowy],inf);
				}
			}
			else insert(id[i][j],T,a[i][j]);
}
int main()
{
	n=read();m=read();T=n*m+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			a[i][j]=read(),ans+=a[i][j];
	build();
	dinic();
	printf("%d\n",ans);
	return 0;
}