方格取数问题

# 题意 给一个$m\times n$的方格，每个方格上有一个数字，要求选取若干不相邻（对角线的不算相邻）的方格并最大化权值和 $n,m\leq100$ <!--more--> # 分析 对棋盘黑白染色，那么两个相邻的方格是异色的 如果在相邻方格之间连边，那么不相邻的含义就是这条边的两个端点不能同时选取 考虑到这是一个二分图，那么我们构造源点和汇点，源点连接黑点，白点连接汇点，黑点连接相邻的白点 那么相当于在这个网络图中求一个割使得源点汇点不连通 于是我们把点的权值映射到边上再求最小割即可 具体建模： - 建立源点汇点 - 源点连接黑点，容量为点权；白点连接汇点，容量为点权 - 黑点连接相邻的白点，容量为INF 在这样的图上求最小割就是去掉的点的和，答案＝所有点的和－最小割 ```cpp #include<cstdio> #include<cstring> #include<queue> #define int long long using namespace std; const int N=1e5+5,M=2e6,INF=0x3f3f3f3f; int n,m,s,t; int sum; struct qxx{int nex,t,v;}; qxx e[M]; int cnt=1,h[N]; void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;} void add_flow(int f,int t,int v){add_path(f,t,v);add_path(t,f,0);} int rk[N]; bool bfs(){ memset(rk,0,sizeof(rk)); queue<int> q; q.push(s),rk[s]=1; while(q.size()){ int u=q.front();q.pop(); for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v; if(w&&!rk[v])rk[v]=rk[u]+1,q.push(v); } } return rk[t]; } int dinic(int u,int flow){ if(u==t)return flow; int x,rest=flow; for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v; if(!w||rk[v]!=rk[u]+1)continue; x=dinic(v,min(rest,w)); if(x)e[i].v-=x,e[i^1].v+=x,rest-=x; else rk[v]=0; } return flow-rest; } signed main(){ scanf("%lld%lld",&n,&m); s=0,t=n*m+1; int qp[105][105]; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%lld",&qp[i][j]); sum+=qp[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int u=(i-1)*m+j; if((i+j)&1){//不是u&1！！！ add_flow(s,u,qp[i][j]); if(i>1)add_flow(u,u-m,INF);//不要把n,m弄混了 if(i<n)add_flow(u,u+m,INF); if(j>1)add_flow(u,u-1,INF); if(j<m)add_flow(u,u+1,INF); } else add_flow(u,t,qp[i][j]); } } int maxflow=0; while(bfs())for(int i;i=dinic(s,INF);)maxflow+=i; printf("%lld",sum-maxflow); return 0; } ```