題目背景

none!

題目描述

在一個有 m*n 個方格的棋盤中，每個方格中有一個正整數(shù)。現(xiàn)要從方格中取數(shù)，使任意 2 個數(shù)所在方格沒有公共邊，且取出的數(shù)的總和最大。試設計一個滿足要求的取數(shù)算法。對于給定的方格棋盤，按照取數(shù)要求編程找出總和最大的數(shù)。

輸入輸出格式

輸入格式：

第 1 行有 2 個正整數(shù) m 和 n，分別表示棋盤的行數(shù)和列數(shù)。接下來的 m 行，每行有 n 個正整數(shù)，表示棋盤方格中的數(shù)。

輸出格式：

程序運行結(jié)束時，將取數(shù)的最大總和輸出

輸入輸出樣例

輸入樣例#1：? 3 3 1 2 3 3 2 3 2 3 1 輸出樣例#1：? 11

說明

m,n<=100

Solution: 　　網(wǎng)絡流套路題。 　　一個點若選，會使得其四方向鄰格不能被選，若以坐標和的奇偶性為基準，則圖會被分為兩部分，不難發(fā)現(xiàn)同一部分的點是不會互相影響的，這恰好是二分圖的形式。 　　我們從$s$向所有奇數(shù)點連點值大小的邊，從偶數(shù)點向$t$連點值大小的邊，然后從奇數(shù)點向受影響的偶數(shù)點連inf的邊。由于要求的是點值和最大的情況，先要使選的情況合法（即使$s,t$不聯(lián)通），且不選的點值和最小，那么這不就是最小割嘛！所以只要用點值和-最小割就是答案了。（好套路的黑白點啊）
代碼： /*Code by 520 -- 8.25*/ #include<bits/stdc++.h> #define il inline #define ll long long #define RE register #define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++) #define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--) #define debug printf("%d %s\n",__LINE__,__FUNCTION__) using namespace std; const int N=100005,inf=233333333,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; int n,m,s,t,dis[N],to[N],net[N],w[N],h[N],cnt=1; int mp[105][105],ans;il int id(int x,int y){return (x-1)*m+y;}il void add(int u,int v,int c){to[++cnt]=v,net[cnt]=h[u],w[cnt]=c,h[u]=cnt;to[++cnt]=u,net[cnt]=h[v],w[cnt]=0,h[v]=cnt; }queue<int>q; il bool bfs(){memset(dis,-1,sizeof(dis));q.push(s),dis[s]=0;while(!q.empty()){RE int u=q.front();q.pop();for(RE int i=h[u];i;i=net[i])if(dis[to[i]]==-1&&w[i]) dis[to[i]]=dis[u]+1,q.push(to[i]);}return dis[t]!=-1; }int dfs(int u,int op){if(u==t)return op;int flow=0,used=0;for(RE int i=h[u];i;i=net[i]){int v=to[i];if(dis[to[i]]==dis[u]+1&&w[i]){used=dfs(to[i],min(op,w[i]));if(!used)continue;flow+=used,op-=used;w[i]-=used,w[i^1]+=used;if(!op)break;}}if(!flow) dis[u]=-1;return flow; }il void init(){scanf("%d%d",&n,&m),t=n*m+1;For(i,1,n) For(j,1,m) {scanf("%d",&mp[i][j]),ans+=mp[i][j];(i+j)&1?add(s,id(i,j),mp[i][j]):add(id(i,j),t,mp[i][j]); }For(i,1,n) For(j,1,m)if((i+j)&1) {For(k,0,3){RE int xx=i+dx[k],yy=j+dy[k];if(xx>0&&xx<=n&&yy>0&&yy<=m) add(id(i,j),id(xx,yy),inf);}}while(bfs()) ans-=dfs(s,inf);cout<<ans; }int main(){init();return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/five20/p/9537561.html

總結(jié)

以上是生活随笔為你收集整理的P2774 方格取数问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。