首页 > > 程序设计 > C/C++ >

BZOJ 2127: happiness(最小割解决集合划分)

2018-06-17 22:04:57来源：未知阅读 ()

Time Limit: 51 Sec Memory Limit: 259 MB
Submit: 2350 Solved: 1138
[Submit][Status][Discuss]

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

1 2
1 1
100 110
1
1000

Sample Output

1210
【样例说明】
两人都选理，则获得100+110+1000的喜悦值。
【数据规模】
对于100%以内的数据，n,m<=100 所有喜悦值均为小于等于5000的非负整数

HINT

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<queue>
  6 using namespace std;
  7 const int MAXN=200001;
  8 const int INF = 1e8;
  9 inline void read(int &n)
 10 {
 11     char c='+';int x=0;bool flag=0;
 12     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 13     while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
 14     n=flag==1?-x:x;
 15 }
 16 int n,m,s,t;
 17 struct node
 18 {
 19     int u,v,flow,nxt;
 20 }edge[MAXN];
 21 int head[MAXN];
 22 int cur[MAXN];
 23 int num=0;
 24 int deep[MAXN];
 25 int tot=0;
 26 void add_edge(int x,int y,int z)
 27 {
 28     edge[num].u=x;
 29     edge[num].v=y;
 30     edge[num].flow=z;
 31     edge[num].nxt=head[x];
 32     head[x]=num++;
 33 }
 34 void add(int x,int y,int z)
 35 {
 36     add_edge(x,y,z);
 37     add_edge(y,x,0);
 38 }
 39 bool BFS()
 40 {
 41     memset(deep,0,sizeof(deep));
 42     deep[s]=1;
 43     queue<int>q;
 44     q.push(s);
 45     while(q.size()!=0)
 46     {
 47         int p=q.front();
 48         q.pop();
 49         for(int i=head[p];i!=-1;i=edge[i].nxt)
 50             if(!deep[edge[i].v]&&edge[i].flow)
 51                 deep[edge[i].v]=deep[edge[i].u]+1,
 52                 q.push(edge[i].v);
 53     }
 54     return deep[t];
 55     
 56 }
 57 int DFS(int now,int nowflow)
 58 {
 59     if(now==t||nowflow<=0)
 60         return nowflow;
 61     int totflow=0;
 62     for(int &i=cur[now];i!=-1;i=edge[i].nxt)
 63     {
 64         if(deep[edge[i].v]==deep[edge[i].u]+1&&edge[i].flow)
 65         {
 66             int canflow=DFS(edge[i].v,min(nowflow,edge[i].flow));
 67             edge[i].flow-=canflow;
 68             edge[i^1].flow+=canflow;
 69             totflow+=canflow;
 70             nowflow-=canflow;
 71             if(nowflow<=0)
 72                 break;
 73         }
 74     
 75     }
 76     return totflow;
 77 }
 78 void Dinic()
 79 {
 80     int ans=0;
 81     while(BFS())
 82     {
 83         memcpy(cur,head,MAXN);
 84         ans+=DFS(s,1e8);
 85     }
 86     printf("%d",tot-(ans>>1));
 87 }
 88 int a[101][101];
 89 int b[101][101];
 90 int mark[101][101];
 91 int main()
 92 {
 93     int n,m;
 94     read(n);read(m);
 95     s=0;t=10001;
 96     memset(head,-1,sizeof(head));
 97     for(int i=1;i<=n;i++)
 98         for(int j=1;j<=m;j++)
 99             cin>>a[i][j],tot+=a[i][j],a[i][j]<<=1;
100     for(int i=1;i<=n;i++)
101         for(int j=1;j<=m;j++)
102             cin>>b[i][j],tot+=b[i][j],b[i][j]<<=1;
103     for(int i=1;i<=n;i++)
104         for(int j=1;j<=m;j++)
105             mark[i][j]=((i-1)*m+j);
106     for(int i=1;i<=n-1;i++)
107         for(int j=1;j<=m;j++)
108         {
109             int p;cin>>p;tot+=p;
110             a[i][j]+=p,a[i+1][j]+=p;
111             add_edge(mark[i][j],mark[i+1][j],p);
112             add_edge(mark[i+1][j],mark[i][j],p);
113         }
114     for(int i=1;i<=n-1;i++)
115         for(int j=1;j<=m;j++)
116         {
117             int p;cin>>p;tot+=p;
118             b[i][j]+=p,b[i+1][j]+=p;
119             add_edge(mark[i][j],mark[i+1][j],p);
120             add_edge(mark[i+1][j],mark[i][j],p);
121         }
122     for(int i=1;i<=n;i++)
123         for(int j=1;j<=m-1;j++)
124         {
125             int p;cin>>p;tot+=p;
126             a[i][j]+=p,a[i][j+1]+=p;
127             add_edge(mark[i][j],mark[i][j+1],p);
128             add_edge(mark[i][j+1],mark[i][j],p);
129         }
130     for(int i=1;i<=n;i++)
131         for(int j=1;j<=m-1;j++)
132         {
133             int p;cin>>p;tot+=p;
134             b[i][j]+=p,b[i][j+1]+=p;
135             add_edge(mark[i][j],mark[i][j+1],p);
136             add_edge(mark[i][j+1],mark[i][j],p);
137         }
138     for(int i=1;i<=n;i++)
139         for(int j=1;j<=m;j++)
140         {
141             add(0,mark[i][j],a[i][j]);
142             add(mark[i][j],t,b[i][j]);
143         }
144     Dinic();
145     return  0;
146 }