题目描述
在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
输入输出格式
输入格式：
第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。
输出格式：
程序运行结束时，将取数的最大总和输出
输入输出样例
输入样例#1：
3 3
1 2 3
3 2 3
2 3 1
输出样例#1：
11
说明
m,n<=100
实际上这个和Exca王者之剑基本上一样..
用那份代码就能A这道题
本来是刷状压dp之后遇到的.
然而数据加强到100状压存不下
其实就是一个黑白染色后跑最小割.
s->黑点 val[i][j]
白点-> val[i][j]
黑点->影响的白点 inf
默认每个点都取，这样跑一遍最大流(既最小割)之后就是答案了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
#include<bits/stdc++.h> using namespace std; inline int read(){ char c=getchar(); int x=0,f=1; while(c<'0'||c>'9'){ if(c=='-')f=-1; c=getchar(); } while(c>='0'&&c<='9'){ x=x*10+c-'0'; c=getchar(); } return x*f; } const int maxn=2e5+10; int n,m,qaq[105][105],head[maxn],cnt,s=0,t=20005; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; struct E{ int next,to,val; }tu[maxn*10]; inline void add(int next,int to,int val){ tu[cnt].next=head[next]; tu[cnt].to=to; tu[cnt].val=val; head[next]=cnt++; } inline void add_edge(int next,int to,int val){ add(next,to,val); add(to,next,0); } queue<int>q; int dis[maxn]; inline bool bfs(){ memset(dis,-1,sizeof(dis)); dis[s]=1; q.push(s); while(!q.empty()){ int x=q.front(); q.pop(); for(int i=head[x];~i;i=tu[i].next){ int u=tu[i].to; if(dis[u]==-1&&tu[i].val){ dis[u]=dis[x]+1; q.push(u); } } } return dis[t]==-1?0:1; } inline int dfs(int x,int low){ if(x==t||!low)return low; int a=0; for(int i=head[x];~i;i=tu[i].next){ int u=tu[i].to; if(dis[u]==dis[x]+1&&tu[i].val){ int to_flow=dfs(u,min(low,tu[i].val)); a+=to_flow; tu[i].val-=to_flow; tu[i^1].val+=to_flow; low-=to_flow; } } if(!a)dis[x]=-1; return a; } long long ans,new_flow; inline void dinic(){ while(bfs()){ while(new_flow=dfs(s,1e9))ans-=new_flow; } cout<<ans; } inline int now(int x,int y){ return (x-1)*n+y; } int main(){ memset(head,-1,sizeof(head)); m=read(),n=read(); for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ qaq[i][j]=read(); ans+=qaq[i][j]; } } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if((i+j)&1){ add_edge(s,now(i,j),qaq[i][j]); } else add_edge(now(i,j),t,qaq[i][j]); } } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ int pos=now(i,j); if((i+j)&1){ for(int k=0;k<=3;k++){ int posx=i+dx[k]; int posy=j+dy[k]; if(posx>m||posx<1||posy>n||posy<1)continue; add_edge(pos,now(posx,posy),1e9); } } } } dinic(); } |
说点什么