方格取数问题
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-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?