「P4313」文理分科

题目描述

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

小 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;
}

完结撒花❀

★,°:.☆(￣▽￣)/$:.°★ 。