Bzoj3894 文理分科

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 667 Solved: 389

Description

文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠

结过）

小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行

描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择

一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式

得到：

1．如果第i行第秒J的同学选择了文科，则他将获得art[i][j]的满意值，如

果选择理科，将得到science[i][j]的满意值。

2．如果第i行第J列的同学选择了文科，并且他相邻（两个格子相邻当且

仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开

心，所以会增加same_art[i][j]的满意值。

3．如果第i行第j列的同学选择了理科，并且他相邻的同学全部选择了理

科，则增加same_science[i]j[]的满意值。

小P想知道，大家应该如何选择，才能使所有人的满意值之和最大。请

告诉他这个最大值。

Input

第一行为两个正整数：n，m

接下来n术m个整数，表示art[i][j]；

接下来n术m个整数．表示science[i][j]；

接下来n术m个整数，表示same_art[i][j]；

Output

输出为一个整数，表示最大的满意值之和

Sample Input

3 4
13 2 4 13
7 13 8 12
18 17 0 5

8 13 15 4
11 3 8 11
11 18 6 5

1 2 3 4
4 2 3 2
3 1 0 4

3 2 3 2
0 2 2 1
0 2 4 4

Sample Output

152

HINT

样例说明

1表示选择文科，0表示选择理科，方案如下：

1 0 0 1

0 1 0 0

1 0 0 0

N,M<=100,读入数据均<=500

网络流最小割

最大权闭合子图

1、从S向学生连边，容量为学文的收益；

2、从学生向T连边，容量为学理的收益；

3、对于一个学生，新建一个点，从S向该点连边，容量为周围人都学文的收益，再从该点向周围学生连边，容量为INF；

4、都学理同理。

答案为权值总和减去最小割

思路倒是好想，然而各种写不对，最后发现，处理一群人学同样课的点的时候，没有向表示该学生自身的点连边……

  1 /*by SilverN*/
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<cmath>
  7 #include<vector>
  8 #include<queue>
  9 using namespace std;
 10 const int mx[5]={0,1,0,-1,0};
 11 const int my[5]={0,0,1,0,-1};
 12 const int INF=1e9;
 13 const int mxn=30010;
 14 int read(){
 15     int x=0,f=1;char ch=getchar();
 16     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 17     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
 18     return x*f;
 19 }
 20 struct edge{
 21     int v,nxt,f;
 22 }e[mxn*50];
 23 int hd[mxn],mct=1;
 24 void add_edge(int u,int v,int f){
 25     e[++mct].v=v;e[mct].nxt=hd[u];e[mct].f=f;hd[u]=mct;return;
 26 }
 27 void insert(int u,int v,int f){
 28     add_edge(u,v,f);
 29     add_edge(v,u,0);
 30     return;
 31 }
 32 int n,m,S,T;
 33 int d[mxn];
 34 bool BFS(){
 35     memset(d,0,sizeof d);
 36     queue<int>q;
 37     d[S]=1;
 38     q.push(S);
 39     while(!q.empty()){
 40         int u=q.front();q.pop();
 41         for(int i=hd[u];i;i=e[i].nxt){
 42             int v=e[i].v;
 43             if(e[i].f && !d[v]){
 44                 d[v]=d[u]+1;
 45                 q.push(v);
 46             }
 47         }
 48     }
 49     return d[T];
 50 }
 51 int DFS(int u,int lim){
 52     if(u==T)return lim;
 53     int f=0,tmp;
 54     for(int i=hd[u];i;i=e[i].nxt){
 55         int v=e[i].v;
 56         if(d[v]==d[u]+1 && e[i].f){
 57             tmp=DFS(v,min(lim,e[i].f));
 58             e[i].f-=tmp;
 59             e[i^1].f+=tmp;
 60             f+=tmp;
 61             lim-=tmp;
 62             if(!lim)return f;
 63         }
 64     }
 65     d[u]=0;
 66     return f;
 67 }
 68 int Dinic(){
 69     int res=0;
 70     while(BFS())res+=DFS(S,INF);
 71     return res;
 72 }
 73 int id[110][110],cnt=0,ed;
 74 void init(){
 75     for(int i=1;i<=n;i++)
 76      for(int j=1;j<=m;j++)
 77          id[i][j]=++cnt;
 78     ed=n*m;
 79     return;
 80 }
 81 int ans=0;
 82 void solve(){
 83     int i,j,x;
 84     for(i=1;i<=n;i++)
 85         for(j=1;j<=m;j++){
 86             x=read();ans+=x;
 87             insert(S,id[i][j],x);//art
 88         }
 89     for(i=1;i<=n;i++)
 90         for(j=1;j<=m;j++){
 91             x=read();ans+=x;
 92             insert(id[i][j],T,x);//science
 93         }
 94     for(i=1;i<=n;i++)
 95         for(j=1;j<=m;j++){
 96             x=read();//same_art
 97             ans+=x;
 98             for(int k=0;k<=4;k++){//从0到4 
 99                 int nx=i+mx[k],ny=j+my[k];
100                 if(nx<1 || nx>n || ny<1 ||ny>m)continue;
101                 insert(id[i][j]+ed,id[nx][ny],INF);
102             }
103             insert(S,id[i][j]+ed,x);
104         }
105     for(i=1;i<=n;i++)
106         for(j=1;j<=m;j++){
107             x=read();//same_sci
108             ans+=x;
109             for(int k=0;k<=4;k++){
110                 int nx=i+mx[k],ny=j+my[k];
111                 if(nx<1 || nx>n || ny<1 ||ny>m)continue;
112                 insert(id[nx][ny],id[i][j]+2*ed,INF);
113             }
114             insert(id[i][j]+2*ed,T,x);
115         }
116     ans-=Dinic();
117     return;
118 }
119 int main(){
120     int i,j,x;
121     n=read();m=read();
122     S=0;T=n*m*3+1;
123     init();
124     solve();
125     printf("%d
",ans);
126     return 0;
127 }