首页 > 代码库 > 洛谷 P2774 方格取数问题
洛谷 P2774 方格取数问题
题目背景
none!
题目描述
在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
输入输出格式
输入格式：
第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。
输出格式：
程序运行结束时，将取数的最大总和输出
输入输出样例
输入样例#1：
3 31 2 33 2 32 3 1
输出样例#1：
11
说明
none!
解题思路
一道和骑士共存问题差不多的题目，二分图黑白染色后跑最大独立集，这里每个白格向四周连边，而不是马能攻击到的地方(废话)。
源代码
#include<queue>#include<cstdio>#include<cstring>#include<algorithm>int n,m;int a[1000][1000]={0};int S=0;inline int id(int x,int y){ return (x-1)*m+y;}int s,t;struct Edge{ int next,to,flow;}e[1000010];int cnt=2,head[1000]={0};void add(int u,int v,int f){ e[cnt]={head[u],v,f}; head[u]=cnt++; e[cnt]={head[v],u,0}; head[v]=cnt++;}int dis[1000]={0};bool bfs(){ memset(dis,0,sizeof(dis)); std::queue<int> q; q.push(s); dis[s]=1; while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(dis[v]||!e[i].flow) continue; dis[v]=dis[u]+1; q.push(v); } } return dis[t]!=0;}int dfs(int u,int f){ if(u==t||f==0) return f; int flow_sum=0; for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(dis[v]!=dis[u]+1||!e[i].flow) continue; int temp=dfs(v,std::min(e[i].flow,f-flow_sum)); e[i].flow-=temp; e[i^1].flow+=temp; flow_sum+=temp; if(flow_sum>=f) break; } if(!flow_sum) dis[u]=-1; return flow_sum;}int dinic(){ int ans=0; while(bfs()) { while(int temp=dfs(s,0x7fffffff)) ans+=temp; } return ans;}int main(){ scanf("%d%d",&n,&m); s=n*m+1,t=s+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]),S+=a[i][j]; int bh[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if((i+j)&1) { add(s,id(i,j),a[i][j]); for(int k=0;k<4;k++) { int x=i+bh[k][0],y=j+bh[k][1]; if(x>=1&&x<=n&&y>=1&&y<=m) add(id(i,j),id(x,y),0x7fffffff); } } else add(id(i,j),t,a[i][j]); } } printf("%d\n",S-dinic()); return 0;}
洛谷 P2774 方格取数问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。