方格取数问题
2022/7/24 23:25:59
本文主要是介绍方格取数问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
link
由于相邻的两个数不能同时选择,于是考虑把相邻的两个元素连边。又由于整张图很明显可以进行黑白染色,于是连边之后的图会形成一张二分图。于是寻找最大的方案就变成了割掉最小的方案,跑最大流最小割即可。
#include<bits/stdc++.h> //#define feyn #define int long long const int N=120; const int M=N*N; const int S=5e6; const int maxn=1e15; using namespace std; inline void read(int &wh){ wh=0;int f=1;char w=getchar(); while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();} while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();} wh*=f;return; } inline int min(int s1,int s2){ return s1<s2?s1:s2; } struct edge{ int t,v,next; }e[S]; int head[M],esum=1; inline void adde(int fr,int to,int val){ e[++esum]=(edge){to,val,head[fr]};head[fr]=esum; } inline void add(int fr,int to,int val){ adde(fr,to,val);adde(to,fr,0); } int m,n,ans,a[N][N],f[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int ss,tt,cnt; int t[M],nt,d[M],q[M],ll,rr; inline bool check(){ //printf("working\n"); t[q[ll=rr=1]=ss]=++nt;d[ss]=0; while(ll<=rr){ int wh=q[ll++]; for(int i=head[wh],th;i;i=e[i].next){ if(e[i].v==0||t[th=e[i].t]==nt)continue; t[th]=nt;d[th]=d[wh]+1;q[++rr]=th; } } return t[tt]==nt; } inline int dinic(int wh,int val){ if(wh==tt)return val; int used=0; for(int i=head[wh],th;i;i=e[i].next){ if(e[i].v==0||d[th=e[i].t]!=d[wh]+1)continue; int now=dinic(th,min(val,e[i].v)); if(now)used+=now,val-=now,e[i].v-=now,e[i^1].v+=now; if(val==0)break; } if(val)d[wh]=-1;return used; } signed main(){ #ifdef feyn freopen("in.txt","r",stdin); #endif read(m);read(n);ss=++cnt,tt=++cnt; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ read(a[i][j]);ans+=a[i][j]; if(i+j&1)add(ss,++cnt,a[i][j]); else add(++cnt,tt,a[i][j]); a[i][j]=cnt; } } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(i+j&1){ for(int k=0;k<4;k++){ int x=i+f[k][0],y=j+f[k][1]; if(x<1||y<1||x>m||y>n)continue; add(a[i][j],a[x][y],maxn); } } } } while(check())ans-=dinic(ss,maxn); printf("%lld\n",ans); return 0; }
这篇关于方格取数问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性