Description

在一個(gè)有m*n 個(gè)方格的棋盤中，每個(gè)方格中有一個(gè)正整數(shù)?，F(xiàn)要從方格中取數(shù)，使任意2 個(gè)數(shù)所在方格沒(méi)有公共邊，且取出的數(shù)的總和最大。試設(shè)計(jì)一個(gè)滿足要求的取數(shù)算法。

Input

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

Output

對(duì)于給定的方格棋盤，按照取數(shù)要求編程找出總和最大的數(shù)，將取數(shù)的最大總和輸出。

Sample Input

3 3
1 2 3
3 2 3
2 3 1?

Sample Output

11

HINT

n,m<=30

?

　　嗯......這道題大概算是自己想出來(lái)的第一道網(wǎng)絡(luò)流的題吧？

　　雖然想了很久，WA了很多發(fā)，但終于A掉了......

　　網(wǎng)絡(luò)流的題真是難想(但這一題還是比較簡(jiǎn)單的)，如果不是我已經(jīng)知道這道題要用網(wǎng)絡(luò)流做，還不知道要想到什么時(shí)候去了......

　　好了，不扯多了，進(jìn)正題：

　　首先，我們發(fā)現(xiàn)直接建模的話非常不好搞，體重的條件不好表示......

　　于是，我們就想，是否可以把我們選完數(shù)之后剩下的數(shù)給表示出來(lái)呢？我們發(fā)現(xiàn)這個(gè)不難做到。只需將棋盤黑白二染色，把黑點(diǎn)、白點(diǎn)各看成一塊，相鄰的格子間有邊相連，不難發(fā)現(xiàn)將黑白兩塊分開(kāi)的割的方案就是不選的點(diǎn)的合法方案（腦補(bǔ)一下應(yīng)該可以搞出來(lái)）。所以最小割即是合法方案中選出的點(diǎn)和最大的方案。于是我們可以從源點(diǎn)向所有黑(白)點(diǎn)連一條容量為這個(gè)格子里的數(shù)的邊，從黑(白)點(diǎn)向相鄰的點(diǎn)連一條容量為INF的邊，再?gòu)陌?黑)點(diǎn)向匯點(diǎn)連一條容量為當(dāng)前格子里的數(shù)的邊，跑一邊最大流即可得出不選的點(diǎn)的最小和，用所有數(shù)字之和減去它就是答案。

　　update:其實(shí)這就是最大獨(dú)立集等于總點(diǎn)數(shù)減去最大匹配數(shù)

　　下面貼代碼：

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define maxm 100010 7 #define INF (1<<25) 8 #define r(j) (j^1) 9 10 using namespace std; 11 typedef long long llg; 12 13 int head[101*101],next[maxm],to[maxm],c[maxm],tt=1; 14 int a[101][101],zx[4]={0,0,1,-1},zy[4]={1,-1,0,0}; 15 int d[maxm],l,r,dep[maxm],ans,tut,s,t,n,m; 16 17 int getint(){ 18 int w=0;bool q=0; 19 char c=getchar(); 20 while((c>'9'||c<'0')&&c!='-') c=getchar(); 21 if(c=='-') q=1,c=getchar(); 22 while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); 23 return q?-w:w; 24 } 25 26 void link(int x,int y,int z){ 27 to[++tt]=y;next[tt]=head[x];head[x]=tt; 28 to[++tt]=x;next[tt]=head[y];head[y]=tt; 29 c[tt^1]=z; 30 } 31 32 bool bfs(){ 33 for(int i=1;i<=t;i++) dep[i]=0; 34 l=r=0;d[r++]=s;dep[s]=1;int u; 35 while(l!=r){ 36 u=d[l++]; 37 for(int i=head[u];i;i=next[i]) 38 if(!dep[to[i]] && c[i]>0){ 39 dep[to[i]]=dep[u]+1; 40 d[r++]=to[i]; 41 } 42 } 43 return dep[t]>0; 44 } 45 46 int dfs(int u,int low){ 47 int res=0,v; 48 if(u==t) return low; 49 if(!low) return 0; 50 for(int i=head[u];i;i=next[i]) 51 if(c[i]>0 && dep[to[i]]==dep[u]+1){ 52 v=dfs(to[i],min(low-res,c[i])); 53 c[i]-=v;c[r(i)]+=v;res+=v; 54 } 55 return res; 56 } 57 58 int main(){ 59 freopen("a.in","r",stdin); 60 freopen("a.out","w",stdout); 61 n=getint();m=getint();s=n*m+1;t=s+1; 62 for(int i=1;i<=n;i++) 63 for(int j=1;j<=m;j++) 64 a[i][j]=getint(); 65 for(int i=1,now(0);i<=n;i++) 66 for(int j=1;j<=m;j++){ 67 now++; 68 if(!((i+j)&1)){ 69 link(s,now,a[i][j]); 70 for(int k=0,x,y,n1;k<4;k++){ 71 x=i+zx[k];y=j+zy[k]; 72 if(x>0 && x<=n && y>0 && y<=m){ 73 n1=(x-1)*m+y; 74 link(now,n1,INF); 75 } 76 } 77 } 78 else link(now,t,a[i][j]); 79 tut+=a[i][j]; 80 } 81 while(bfs()) 82 while(int tot=dfs(s,INF)) ans+=tot; 83 printf("%d\n",tut-ans); 84 return 0; 85 }

轉(zhuǎn)載于:https://www.cnblogs.com/lcf-2000/p/5551356.html

總結(jié)

以上是生活随笔為你收集整理的codevs 1907 方格取数 3的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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