[BZOJ]2127happiness 最大权闭合图再谈(一)

Description

高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。

Input

第一行两个正整数n，m。接下来是六个矩阵第一个矩阵为n行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学选择文科获得的喜悦值。第二个矩阵为n行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学选择理科获得的喜悦值。第三个矩阵为n-1行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i+1行第j列的同学同时选择文科获得的额外喜悦值。第四个矩阵为n-1行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i+1行第j列的同学同时选择理科获得的额外喜悦值。第五个矩阵为n行m-1列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i行第j+1列的同学同时选择文科获得的额外喜悦值。第六个矩阵为n行m-1列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i行第j+1列的同学同时选择理科获得的额外喜悦值。

Output

输出一个整数，表示喜悦值总和的最大值

Sample Input

Sample Output

本题做法很多，大致有三种：

解法一：

利用最小割考虑。

对于原图中所有相邻的两个人A，B，我们建边：

s->A:cost[A文]+c[文][A][B]/2,s->B:cost[B文]+c[文][A][B]/2;

A->t:cost[A理]+c[理][A][B]/2,B->t:costB[理]+c[理][A][B]/2;

A<-->B:c[文][A][B]/2+c[理][A][B]/2

这样会出现两种割，分别对应两种相同，一种选文一种选理。

code：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #define maxn 10000 using namespace std; int n,m; int s,t; int tot=1; int fir[200000],en[200000],nex[200000],f[200000]; void ins(int a,int b,int c,int d){ nex[++tot]=fir[a]; fir[a]=tot; en[tot]=b; f[tot]=c; nex[++tot]=fir[b]; fir[b]=tot; en[tot]=a; f[tot]=d; } int ch[200][200][2]; int flow; int d[200000],now[200000],num[200000],pre[200000],his[200000]; void sap(){ flow=0; for (int i=0;i<=t;i++){ now[i]=fir[i]; d[i]=num[i]=0; } num[0]=t; int aug=0x7fffffff; bool flag; int i=s; while (d[s]
        
         0&&d[i]==d[en[k]]+1){ aug=min(aug,f[k]); flag=true; now[i]=k; pre[en[k]]=i; i=en[k]; if (i==t){ flow+=aug; while (i!=s){ i=pre[i]; f[now[i]]-=aug; f[now[i]^1]+=aug; } aug=0x7fffffff; } break; } if (flag) continue; int k1=0,minn=t; for (int k=fir[i];k;k=nex[k]) if (f[k]>0&&minn>d[en[k]]){ k1=k; minn=d[en[k]]; } now[i]=k1; if (!--num[d[i]]) return; d[i]=minn+1; num[d[i]]++; if (i!=s){ i=pre[i]; aug=his[i]; } } } int sum=0; int main(){ // freopen("2127.in","r",stdin); // freopen("2127.out","w",stdout); scanf("%d%d",&n,&m); s=n*m+1,t=n*m+2; for (int i=1;i<=n;i++) //割文 去理 for (int j=1;j<=m;j++){ scanf("%d",&ch[i][j][0]); sum+=ch[i][j][0]; ch[i][j][0]*=2; } for (int i=1;i<=n;i++) //割理 去文 for (int j=1;j<=m;j++){ scanf("%d",&ch[i][j][1]); sum+=ch[i][j][1]; ch[i][j][1]*=2; } for (int i=1;i<=n-1;i++) for (int j=1;j<=m;j++){ int tmp; scanf("%d",&tmp); sum+=tmp; ins((i-1)*m+j,i*m+j,tmp,tmp); ch[i][j][0]+=tmp; ch[i+1][j][0]+=tmp; } for (int i=1;i<=n-1;i++) for (int j=1;j<=m;j++){ int tmp; scanf("%d",&tmp); sum+=tmp; ins((i-1)*m+j,i*m+j,tmp,tmp); ch[i][j][1]+=tmp; ch[i+1][j][1]+=tmp; } for (int i=1;i<=n;i++) for (int j=1;j<=m-1;j++){ int tmp; scanf("%d",&tmp); sum+=tmp; ins((i-1)*m+j,(i-1)*m+j+1,tmp,tmp); ch[i][j][0]+=tmp; ch[i][j+1][0]+=tmp; } for (int i=1;i<=n;i++) for (int j=1;j<=m-1;j++){ int tmp; scanf("%d",&tmp); sum+=tmp; ins((i-1)*m+j,(i-1)*m+j+1,tmp,tmp); ch[i][j][1]+=tmp; ch[i][j+1][1]+=tmp; } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++){ ins(s,(i-1)*m+j,ch[i][j][0],0); ins((i-1)*m+j,t,ch[i][j][1],0); } sap(); printf("%d",sum-flow/2); return 0; }
        
       
      
     
    
   
  

解法二：

还是利用最小割考虑。

对于原图中所有相邻的两个人A，B，新建辅助节点C，D，建边：

s->A:cost[A文]，s->B:cost[B文]；

A->t:cost[A理]，B->t:costB[理]；

C->A:INF;C->B:INF;A->D:INF;B->D:INF; 用来帮助我们表示三种取法。(最大权闭合图)

S->C:c[文][A][B]；D->T:c[理][A][B];

这样也只会出现两种割。

code by gsq:

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; int getx() { char c;int x; for (c=getchar();c<'0'||c>'9';c=getchar()); for (x=0;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+c-'0'; return x; } bool upmin(int &a,const int &b){return a>b a=b,1:0;} const int INF=~0U>>1; const int MAX_N=50050,MAX_M=1200000; int first[MAX_N],next[MAX_M],to[MAX_M],f[MAX_M]; int tal=1; int sum; void tjb(int x,int y,int F){ if (F!=INF) sum+=F; next[++tal]=first[x]; first[x]=tal; to[tal]=y; f[tal]=F; next[++tal]=first[y]; first[y]=tal; to[tal]=x; f[tal]=0; } int pre[MAX_N],cur[MAX_N],dis[MAX_N],gap[MAX_N],his[MAX_N]; int sap(int S,int T,int Size){ for (int i=0;i<=Size;++i) cur[i]=first[i], dis[i]=gap[i]=0; int maxflow=0,aug=INF; int u=pre[S]=S; gap[0]=Size; while (dis[S]
       
        
 
        
 
        
 
        
解法三：
 
        
将原问题转化，转化为：所有人现在都选理，然后每个人选择变成文会带来多少收益或损失，利用最大权闭合图考虑。
 
        
同样的，也要新建辅助节点C,D，如下：
 
        
C->A:INF;C->B:INF;A->D:INF;B->D:INF;(C点是指全部选文科，D是指有一个选了文科就要付出“共同选理科的代价”)
 
        
剩下的利用最大权闭合图考虑，用文的获益减去理得获益，如果是正的，由s连向他，如果是负的，由他连向t。
 
        
code by LDD：
 
        

        
#include
         
          
#include
          
            #include
           
             #include
            
              #include
             
               #include
              
                using namespace std; int get_int(){ int x=0;char c;int t=0; for (c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar()); if (c=='-'){t=1;c=getchar();} for (;c>='0'&&c<='9';c=getchar()){x*=10;x+=c-48;} if (t) x=-x;return x; } bool upmin(int &v,int x){if (x
               
                =x2[i][j]) { zh+=x1