题目描述
在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
输入输出格式
输入格式：
第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。
输出格式：
程序运行结束时，将取数的最大总和输出
输入输出样例
说明
该题求的是 最大独立集团权值和 因为所取的点没有两点是相邻的
所以把相邻点连起来！
由前面二分匹配知 最大独立集团=顶点数-最小覆盖点 加上权值也是一样的
所以最大独立集团权值和 ==总权值-最小覆盖点权值和
所以求出最小覆盖点权值和即可 且=最小割=最大流
奇偶建图
源点-奇数 奇数和所有相邻的建图 偶数 -汇点
按照我自己的理解
先按照矛盾条件建图 （也就是 相邻的相连)
然后跑最大流 也就是最小割
最小的消耗使得(该矛盾图无路可走 也就是没有任何一个矛盾成立 ） 剩下的都是符合题意的流
sum-最小割即为答案！
离散化要*m dubug了一个小时qwq
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f const int N=10000+5; const int M=200000+5; int head[M],pos,m,n; struct Edge { int to,nex=-1,v; }edge[M]; void init() { pos=-1; CLR(head,-1); } void add(int a,int b,int c) { edge[++pos].nex=head[a]; head[a]=pos; edge[pos].to=b; edge[pos].v=c; edge[++pos].nex=head[b]; head[b]=pos; edge[pos].to=a; edge[pos].v=0; } int deth[N]; int bfs(int s,int t) { CLR(deth,0); queue<int>q; deth[s]=1; q.push(s); while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];i!=-1;i=edge[i].nex) { int v=edge[i].to; if(edge[i].v>0&&deth[v]==0) { deth[v]=deth[u]+1; q.push(v); } } } return deth[t]; } int dfs(int s,int t,int dis) { if(s==t)return dis; for(int i=head[s];i!=-1;i=edge[i].nex) { int v=edge[i].to; if(deth[v]==deth[s]+1&&edge[i].v!=0) { int di=dfs(v,t,min(dis,edge[i].v)); if(di>0) { edge[i].v-=di; edge[i^1].v+=di; return di; } } } return 0; } int dinic(int s,int t) { int ans=0; while(bfs(s,t)) while(int di=dfs(s,t,inf)) ans+=di; return ans; } int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; int id(int x,int y) { return (x-1)*m+y+2; } int main() { RII(n,m); int s=1,t=2; init(); ll sum=0; rep(i,1,n) rep(j,1,m) { int x;RI(x); sum+=x; if((i+j)&1) add(s,id(i,j),x); else add(id(i,j),t,x); if((i+j)&1) { rep(k,0,3) { int x=i+dx[k]; int y=j+dy[k]; if(x>=1&&x<=n&&y>=1&&y<=m) add(id(i,j),id(x,y),inf); } } } cout<<sum-dinic(s,t); }