【BZOJ1475】方格取数 [最小割]

方格取数

Time Limit: 5 Sec Memory Limit: 64 MB
[Submit][Status][Discuss]

Description

　　在一个n*n的方格里，每个格子里都有一个正整数。从中取出若干数，使得任意两个取出的数所在格子没有公共边，且取出的数的总和尽量大。

Input

　　第一行一个数n；接下来n行每行n个数描述一个方阵

Output

　　仅一个数，即最大和

Sample Input

　　2
　　1 2
　　3 5

Sample Output

HINT

　　n<=30

Main idea

　　给定一个矩阵，取了一个点就不能取上下左右的点了，求能取出的最大价值。

Solution

　　求的显然是最大权独立集，最大权独立集=总权-最小权覆盖集，对于最小权覆盖集我们用最小割来解。

　　由于取了一个点，不能取上下左右的点，即i+-1 or j+-1，那么显然是一个二分图，根据奇偶分类。

　　然后就是一个最小割的模型，我们左边的点向上下左右的点连边，容量为INF(必然不是割)，然后跑最大流即可。

Code

  1 #include<iostream>    
  2 #include<string>    
  3 #include<algorithm>    
  4 #include<cstdio>    
  5 #include<cstring>    
  6 #include<cstdlib>    
  7 #include<cmath>    
  8 #include<map>  
  9 using namespace std;  
 10   
 11 const int ONE=1001;
 12 const int TWO=100001;
 13 const int INF=2147483640;
 14  
 15 int n,m;
 16 int tot=0;
 17 int res,tou,wei,S,T;
 18 int Dep[ONE],q[TWO],ans;
 19 int a[ONE][ONE],PD[ONE][ONE],BI[ONE][ONE];
 20 int next[TWO],first[TWO],go[TWO],w[TWO];
 21 int E[ONE];
 22      
 23 int get()    
 24 {    
 25         int res=1,Q=1;char c;    
 26         while( (c=getchar())<48 || c>57 ) 
 27         if(c=='-')Q=-1; 
 28         res=c-48;     
 29         while( (c=getchar())>=48 && c<=57 )    
 30         res=res*10+c-48;    
 31         return res*Q;    
 32 }         
 33  
 34 int Add(int u,int v,int z)
 35 {
 36         next[++tot]=first[u];   first[u]=tot;   go[tot]=v;  w[tot]=z;
 37         next[++tot]=first[v];   first[v]=tot;   go[tot]=u;  w[tot]=0;
 38 }
 39  
 40 int Bfs()
 41 {
 42         memset(Dep,0,sizeof(Dep));  
 43         q[1]=0;
 44         tou=0;  wei=1;  Dep[0]=1;
 45         for(int u=0;u<=n*n;u++) E[u]=first[u];
 46         while(tou<wei)
 47         {
 48             int u=q[++tou];
 49             for(int e=first[u];e;e=next[e])
 50             {
 51                 int v=go[e];
 52                 if(Dep[v] || !w[e])continue;    
 53                 Dep[v]=Dep[u]+1;
 54                 q[++wei]=v;
 55             }
 56         }
 57         return (Dep[T]>0);       
 58 }
 59    
 60 int Dfs(int u,int Limit)
 61 {
 62         if(u==T || !Limit) return Limit;
 63         int flow=0,f;
 64         for(int &e=E[u];e;e=next[e])
 65         {
 66             int v=go[e];
 67             if(Dep[v]!=Dep[u]+1 || !w[e]) continue;
 68             f=Dfs(v,min(Limit,w[e]));
 69             w[e]-=f;
 70             w[e^1]+=f;
 71             Limit-=f;
 72             flow+=f;
 73             if(!Limit)break;
 74         }
 75         return flow;
 76 }
 77  
 78 void Build(int i,int j)
 79 {
 80         if(BI[i-1][j])  Add(BI[i][j],BI[i-1][j],INF);   
 81         if(BI[i][j-1])  Add(BI[i][j],BI[i][j-1],INF);
 82         if(BI[i+1][j])  Add(BI[i][j],BI[i+1][j],INF);
 83         if(BI[i][j+1])  Add(BI[i][j],BI[i][j+1],INF);
 84 }
 85  
 86 int main()  
 87 {
 88         n=get();
 89         for(int i=1;i<=n;i++)
 90         for(int j=1;j<=n;j++)
 91         {
 92             a[i][j]=get();
 93             ans+=a[i][j];
 94             if( i%2!=j%2 ) PD[i][j]=1;
 95             BI[i][j]=++tot;
 96         }
 97          
 98         S=0;    T=n*n+1;    tot=1;
 99         for(int i=1;i<=n;i++)
100         for(int j=1;j<=n;j++)
101         {
102             if(PD[i][j]) Add(S,BI[i][j],a[i][j]);
103             else Add(BI[i][j],T,a[i][j]);
104             if(PD[i][j])    Build(i,j);
105         }
106          
107         while(Bfs())
108         res+=Dfs(0,INF);
109          
110         printf("%d",ans-res);
111 }

View Code