题目描述
文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠结过）
小 P 所在的班级要进行文理分科。他的班级可以用一个 \(n\times m\) 的矩阵进行描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到：
-
如果第 \(i\) 行第 \(j\) 列的同学选择了文科，则他将获得 \(art_{i,j}\) 的满意值，如果选择理科，将得到 \(science_{i,j}\) 的满意值。
-
如果第 \(i\) 行第 \(j\) 列的同学选择了文科，并且他相邻（两个格子相邻当且仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开心，所以会增加 \(same\text{\underline{ }}art_{i,j}\) 的满意值。
-
如果第 \(i\) 行第 \(j\) 列的同学选择了理科，并且他相邻的同学全部选择了理科，则增加 \(same\text{\underline{ }}science_{i,j}\) 的满意值。
小 P 想知道，大家应该如何选择，才能使所有人的满意值之和最大。请告诉他这个最大值。
输入格式
输入第一行为两个正整数 \(n,m\)。
接下来 \(n\) 行 \(m\) 个整数，第 \(i\) 行第 \(j\) 个整数表示 \(art_{i,j}\)；
接下来 \(n\) 行 \(m\) 个整数，第 \(i\) 行第 \(j\) 个整数表示 \(science_{i,j}\)；
接下来 \(n\) 行 \(m\) 个整数，第 \(i\) 行第 \(j\) 个整数表示 \(same\text{\underline{ }}art_{i,j}\)；
接下来 \(n\) 行 \(m\) 个整数，第 \(i\) 行第 \(j\) 个整数表示 \(same\text{\underline{ }}science_{i,j}\)。
输出格式
输出为一个整数，表示最大的满意值之和。
样例 #1
样例输入 #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\leq 100\)，读入数据均 \(\leq 500\)。
SOLUTION
考虑最小割，通过连\(INF\)边强制让相邻的点不割距离超过\(D\)的边
如果没有光滑性限制
这个题就是一个ruozhi简单的最小割
在第\(r\)层的点\(x(i,j)\)与下一层 \(y\) 的连\((x,y,v[r][i][j])\)
（因为是每一\((i,j)\)选一个切割点）
这种选择的就可以考虑最小割
那有光滑限制怎么办呢
其实就是不能切割相邻的\((x,y)\)和\((x',y')\)的\(r\)距离要小于等于D
那么我们就保证相邻的点的\(r\)距离大于D的不会被切割好了
\((x,y)→(x',y'),flow=INF\)
over！
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+2,INF=1e9,M=1e2+2;
struct node{ll to,val,nxt;}e[N*2];
ll a,n,vis[N],d[N],hd[N],m,ans,cnt,sum,S,T;
const ll dx[]={0,1,0,-1,0},dy[]={1,0,-1,0,0};
bool ok(ll x,ll y){return x>=1&&x<=n&&y>=1&&y<=m;}
void add(ll x,ll y,ll c){
e[++cnt]={y,c,hd[x]};
hd[x]=cnt;
}
bool bfs(){
queue<ll>q;
memset(d,0,sizeof(d));
q.push(S);d[S]=1;
while(!q.empty()){
ll x=q.front();q.pop();
for(ll i=hd[x];~i;i=e[i].nxt){
ll y=e[i].to,w=e[i].val;
if(w&&!d[y]){
d[y]=d[x]+1;
q.push(y);
if(y==T) return 1;
}
}
}
return 0;
}
ll dinic(ll x,ll flow){
if(x==T) return flow;
ll r=flow,k;
for(ll i=hd[x];~i&&r;i=e[i].nxt){
ll y=e[i].to,w=e[i].val;
if(w&&d[y]==d[x]+1){
k=dinic(y,min(r,w));
if(!k)d[y]=0;
e[i].val-=k;
e[i^1].val+=k;
r-=k;
if(!r) return flow;
}
}
return flow-r;
}
int main(){
scanf("%lld%lld",&n,&m);
cnt=1;
S=0,T=3*n*m+1;
memset(hd,-1,sizeof(hd));
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
scanf("%lld",&a);
sum+=a;
ll x=(i-1)*m+j;
add(S,x,a),add(x,S,0);
}
}
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
scanf("%lld",&a);
sum+=a;
ll x=(i-1)*m+j;
add(x,T,a),add(T,x,0);
}
}
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
scanf("%lld",&a);
sum+=a;
ll x=(i-1)*m+j+n*m;
add(S,x,a),add(x,S,0);
}
}
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
scanf("%lld",&a);
sum+=a;
ll x=(i-1)*m+j+n*m*2;
add(x,T,a),add(T,x,0);
}
}
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
ll x=(i-1)*m+j;
for(ll k=0;k<=4;k++){
ll xi=i+dx[k],yj=j+dy[k];
if(!ok(xi,yj))continue;
ll y=(xi-1)*m+yj;
add(x+n*m,y,INF),add(y,x+n*m,0);
add(y,x+n*m*2,INF),add(x+n*m*2,y,0);
}
}
}
while(bfs()){
ans+=dinic(S,INF);
}
printf("%lld",sum-ans);
return 0;
}
完结撒花❀
★,°:.☆(￣▽￣)/$:.°★ 。
标签：return,luogu,行第,flow,整数,选择,文理,P4313,ll From： https://www.cnblogs.com/Aurora1217/p/17206100.html