网络流24题-方格取数-白红宇

网络流24题-方格取数

阅读量：7026 次

发布时间：2019-06-28

本文共 2661 字，大约阅读时间需要 8 分钟。

方格中取数若干，两两不相邻，求最大选数和。

样例：

3 3

1 2 3

3 2 3

2 3 1

输出：

ans=2+3+3+3=11

黑白染色

建成二分图：

中间这些边连成INF(即不限制流量)

其实就是求最大独立集

定理：|二分图最大独立集|=|顶点数|-|二分图最大匹配数|

这个，我不会证明。

所以：|二分图最大独立集|=|总价值|-|二分图最大匹配价值|

考虑构图：s=>黑点=>白点=>t

首先，对与第[i][j]格，有价值为val[i][j]

edge(s,黑点，val[i][j])

edge(白点，t,val[i][j])

然后，对所有黑点

edge(黑点,相邻白点，INF)

令，|总价值|=sum=∑∑val[i][j] (1<=i<=n,1<=j<=m)

|二分图最大匹配价值|<=>|最小割|<=>|最大流| 这个就不分析了。

ans=sum-MaxFlow(G)

于是，代码呼之欲出

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
              10 #include 
              
                11 using namespace std; 12 13 inline void read(int &ans){ 14 ans=0;char x=getchar();int f=1; 15 while(x<'0'||x>'9'){ if(x=='-')f=-1;x=getchar();} 16 while(x>='0'&&x<='9')ans=ans*10+x-'0',x=getchar(); 17 ans*=f; 18 } 19 const int MAXN=30+10; 20 const int MAXV=MAXN*MAXN; 21 const int MAXE=MAXV<<4; 22 const int INF=2e9; 23 struct net{ int v,next,c;}E[MAXE]; 24 int head[MAXV],tot,n,m; 25 int vis[MAXN][MAXN],val[MAXN][MAXN],cnt; 26 void edge(int u,int v,int c){ 27 E[tot]=(net){v,head[u],c},head[u]=tot++; 28 E[tot]=(net){u,head[v],0},head[v]=tot++; 29 } 30 struct Net{ 31 int s,t; 32 int dep[MAXV],cur[MAXV]; 33 void init(int a,int b){ 34 s=a,t=b,memset(head,-1,sizeof(head)); 35 } 36 bool bfs(){ 37 memset(dep,0,sizeof(dep)); 38 queue
               
                q; 39 dep[s]=1,q.push(s); 40 while(!q.empty()){ 41 int u=q.front();q.pop(); 42 for(int i=head[u];~i;i=E[i].next){ 43 int v=E[i].v; 44 if(!dep[v]&&E[i].c>0){ 45 dep[v]=dep[u]+1; 46 q.push(v); 47 } 48 } 49 if(dep[t])return true; 50 } 51 return false; 52 } 53 int dfs(int u,int f){ 54 if(u==t)return f; 55 int ans=0,cup; 56 for(int &i=cur[u];~i;i=E[i].next){ 57 int v=E[i].v; 58 if(E[i].c>0&&dep[v]==dep[u]+1){ 59 cup=dfs(v,min(f-ans,E[i].c)); 60 E[i].c-=cup; 61 E[i^1].c+=cup; 62 ans+=cup; 63 if(ans==f)return ans; 64 } 65 } 66 return ans; 67 } 68 int work(){ 69 int ans=0; 70 while(bfs()){ 71 for(int i=0;i<=t;i++)cur[i]=head[i]; 72 ans+=dfs(s,INF); 73 } 74 return ans; 75 } 76 }a; 77 78 int Tx[4]={ 1,-1,0,0}; 79 int Ty[4]={ 0,0,-1,1}; 80 int main(){ 81 read(n),read(m); 82 int s=n*m+1,t=s+1; 83 a.init(s,t); 84 for(int i=1;i<=n;i++) 85 for(int j=1;j<=m;j++) 86 read(val[i][j]),vis[i][j]=++cnt; 87 int SUM=0; 88 for(int i=1;i<=n;i++) 89 for(int j=1;j<=m;j++){ 90 SUM+=val[i][j]; 91 if((i+j)&1)edge(s,vis[i][j],val[i][j]); 92 else edge(vis[i][j],t,val[i][j]); 93 int I,J; 94 if((i+j)&1) 95 for(int k=0;k<4;k++){ 96 I=i+Tx[k],J=j+Ty[k]; 97 if(I<1||I>n||J<1||J>m)continue; 98 edge(vis[i][j],vis[I][J],INF); 99 }100 }101 cout<
                
                 <