bzoj 1324: Exca王者之剑

相邻格子不能取，求最大值

最大流

#include
#include
#include
using namespace std;
int head[100001];
struct map
{int f;int s,t;int next;
}a[400001];
int b[5001];
int edge;
int p;
int q[400001],d[400001];
int map[101][101];
struct mo
{int x,y;
}move[4];
inline void add(int s,int t,int f)
{a[edge].next=head[s];head[s]=edge;a[edge].s=s;a[edge].t=t;a[edge].f=f;
}
inline bool bfs()
{int l=0,r=0;memset(q,0,sizeof(q));r++;q[r]=0;memset(d,-1,sizeof(d));d[0]=0;int i,k;while(l0&&d[a[i].t]==-1){d[a[i].t]=d[k]+1;r++;q[r]=a[i].t;}}}if(d[p]>=0)return true;return false;
}
inline int dfs(int k,int s)
{if(k==p)return s;int t=s;int i;for(i=head[k];i!=0;i=a[i].next){if(d[a[i].t]==d[k]+1&&a[i].f>0){int xx=dfs(a[i].t,min(s,a[i].f));a[i].f-=xx;if(i%2==0)a[i-1].f+=xx;elsea[i+1].f+=xx;s-=xx;}}return t-s;
}
inline int maxflow()
{int s=0;while(bfs())s+=dfs(0,2100000000);return s;
}
int main()
{move[1].x=1;move[1].y=0;move[2].x=-1;move[2].y=0;move[3].x=0;move[3].y=1;move[4].x=0;move[4].y=-1;int n,m;scanf("%d%d",&n,&m);int i,j,k;int sum=0;for(i=1;i<=n;i++){for(j=1;j<=m;j++){scanf("%d",&map[i][j]);sum+=map[i][j];}}for(i=1;i<=n;i++){for(j=1;j<=m;j++){if((i+j+1)%2==1){edge++;add(0,(i-1)*m+j,map[i][j]);edge++;add((i-1)*m+j,0,0);for(k=1;k<=4;k++){int x=i+move[k].x,y=j+move[k].y;if(x<1||x>n||y<1||y>m)continue;edge++;add((i-1)*m+j,(x-1)*m+y,2100000000);edge++;add((x-1)*m+y,(i-1)*m+j,0);}}else{edge++;add((i-1)*m+j,n*m+1,map[i][j]);edge++;add(n*m+1,(i-1)*m+j,0);}}}p=n*m+1;printf("%d\n",sum-maxflow());return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！