文理分科
题目描述
文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠结过）
小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到：
如果第i行第秒J的同学选择了文科，则他将获得art[i][j]的满意值，如果选择理科，将得到science[i][j]的满意值。
如果第i行第J列的同学选择了文科，并且他相邻（两个格子相邻当且仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开心，所以会增加same_art[i][j]的满意值。
如果第i行第j列的同学选择了理科，并且他相邻的同学全部选择了理科，则增加same_science[i][j]的满意值。
小P想知道，大家应该如何选择，才能使所有人的满意值之和最大。请告诉他这个最大值。
输入格式
第一行为两个正整数：n，m
接下来n行m个整数，表示art[i][j]；
接下来n行m个整数．表示science[i][j]；
接下来n行m个整数，表示same_art[i][j]；
接下来n行m个整数，表示same_science[i][j]；
输出格式
输出为一个整数，表示最大的满意值之和
输入输出样例
输入 #1复制
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
输出 #1复制
152
说明/提示
样例说明
1表示选择文科，0表示选择理科，方案如下：
1 0 0 1
0 1 0 0
1 0 0 0
数据范围
N,M<=100,读入数据均<=500
很明显的一道集合分割，对于每个点非黑即白，于是我们可以采用，最小割。
对于每个点的两种状态，我们分别用S连向点，和点连向T。对于点和附近的点的共同收益，我们建立新的节点，让S连向新的节点，流量为增加的收益，新的节点连向相连的点和本身。对于连向T的同理。
这样不同的最小割就代表了不同的方案，答案就是总的值，减去最小割。
AC代码：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=100010,M=1000010;
const int dx[]={0,0,1,0,-1},dy[]={0,1,0,-1,0};
int n,m,s,t,base,h[N],res;
int head[N],nex[M],to[M],w[M],tot=1;
inline void ade(int a,int b,int c){
to[++tot]=b; w[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c){
ade(a,b,c); ade(b,a,0);
}
inline int id(int x,int y){
return m*(x-1)+y;
}
int bfs(){
queue<int> q; q.push(s); memset(h,0,sizeof h); h[s]=1;
while(q.size()){
int u=q.front(); q.pop();
for(int i=head[u];i;i=nex[i]){
if(!h[to[i]]&&w[i]){
h[to[i]]=h[u]+1; q.push(to[i]);
}
}
}
return h[t];
}
int dfs(int x,int f){
if(x==t) return f;
int fl=0;
for(int i=head[x];i&&f;i=nex[i]){
if(h[to[i]]==h[x]+1&&w[i]){
int mi=dfs(to[i],min(w[i],f));
w[i]-=mi; w[i^1]+=mi; fl+=mi; f-=mi;
}
}
if(!fl) h[x]=-1;
return fl;
}
int dinic(){
int res=0;
while(bfs()) res+=dfs(s,inf);
return res;
}
signed main(){
cin>>n>>m; base=n*m; s=0; t=base*3+10; int x;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>x,add(s,id(i,j),x),res+=x;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>x,add(id(i,j),t,x),res+=x;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>x; add(s,id(i,j)+base,x); res+=x;
for(int k=0;k<5;k++){
int tx=i+dx[k]; int ty=j+dy[k];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m){
add(id(i,j)+base,id(tx,ty),inf);
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>x; add(id(i,j)+base*2,t,x); res+=x;
for(int k=0;k<5;k++){
int tx=i+dx[k]; int ty=j+dy[k];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m){
add(id(tx,ty),id(i,j)+base*2,inf);
}
}
}
}
cout<<res-dinic()<<endl;
return 0;
}
百威成长空间 52人发布
