题解——P4313 文理分科

Augury · 2023-04-09 09:39:24 · 题解

题解——P4313 文理分科

看了一下题解，似乎没有最大权闭合子图的做法。

发一篇题解，希望管理大大能给过。

个人认为最大权闭合子图要好理解一些。

前置知识

最大权闭合子图

如果您不知道什么是最大权闭合子图，您可以去看看P2762 太空飞行计划问题

题意

有 n\times m 个人，在一个 n\times m 的矩阵中。

• 如果第 i 行第 j 列的同学选择了文科，则他将获得 art_{i,j} 的满意值，如果选择理科，将得到 science_{i,j} 的满意值。

• 如果第 i 行第 j 列的同学选择了文科，并且他相邻的同学全部选择了文科，则增加 sameart_{i,j} 的满意值。

• 如果第 i 行第 j 列的同学选择了理科，并且他相邻的同学全部选择了理科，则增加 samescience_{i,j} 的满意值。

求总满意值最大可能是多少。

思路

我们发现，如果考虑先把每个点拆成两个点，一个表示选择文科，一个表示选择理科，那么指定会选重。

于是，我们假定初始所有人都选的文科，然后我们考虑策反让一部分人选择理科。

考虑一个人从文科改成理科会产生哪些贡献。

1. 首先，会直接获得 science_{i,j}-art_{i,j} 的收益。
2. 其次，因为这个人本身不再是文科生，所以他自己的 sameart 消失。
3. 因为这个人不再选择文科，所以他周围的四个点不再满足 sameart 的生效条件，所以这些点的 sameart 消失。

所以，我们知道了，如果现在选择让一个人选择理科，周围这 5 个点的 sameart 就会消失。

然后考虑 samescience 的贡献。

1. 首先，我们一定会得到 samescience_{i,j} 的收益。
2. 其次，这个点附近的五个点都要选择理科。

于是，我们考虑将每个点拆成三个：

1. 价值为 science_{i,j}-art_{i,j} 的点，表示一个人从文科改成理科可以直接获得的收益。
2. 价值为 -sameart_{i,j} 的点，表示周围几个点选择理科的额外亏损。
3. 价值为 samescience_{i,j} 的点，表示周围几个点都选择理科的额外收益。

然后就可以套用最大权闭合子图了

1. 如果我要选择一个点的 1 类点，我就要选择周围这 5 个点的 2 类点。
2. 如果我要选择一个点的 3 类点，我就要选择这个点周围的 5 个 1 类点。

这正是最大权闭合子图的模型。

然后，直接建图跑网络流即可。

注意，因为我们计算的是相对于全选文科的贡献，所以得到答案后要加上全选文科的收益。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int ans=0,op=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')op=1;ch=getchar();}
    while(ch>='0'&&ch<='9'){ans=(ans<<3)+(ans<<1)+(ch^48);ch=getchar();}
    if(op)ans=-ans;
    return ans;
}
const int maxn=110;
const int maxnode=3e4+10;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
const int inf=0x3f3f3f3f;
int n,m;
int ar[maxn][maxn],sc[maxn][maxn],sa[maxn][maxn],ss[maxn][maxn];
int num[maxn][maxn];//每个点的编号
int node=0;//点数计数器
int ans=0;//全选文科的答案
int s,t;
struct edge{
    int u,v,f,nxt;
}e[maxnode<<5];
int fst[maxnode],ce=0;
int dep[maxnode],gap[maxnode];
int maxflow=0;
int ex;
void add(int u,int v,int f){
    e[ce]=(edge){u,v,f,fst[u]};
    fst[u]=ce++;
    e[ce]=(edge){v,u,0,fst[v]};
    fst[v]=ce++;
}
void build(){
    memset(fst,-1,sizeof(fst));
    s=0,t=node*3+1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int val=sc[i][j]-ar[i][j];//改成理科的直接贡献
            if(val>=0)add(s,num[i][j],val),ex+=val;
            else add(num[i][j],t,-val);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            add(num[i][j],num[i][j]+node,inf);
            add(num[i][j]+node,t,sa[i][j]);//改成理科的额外亏损
            for(int dir=0;dir<4;dir++){
                int nx=i+dx[dir],ny=j+dy[dir];
                if(nx<1||nx>n||ny<1||ny>m)continue;
                add(num[i][j],num[nx][ny]+node,inf);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            add(num[i][j]+(node<<1),num[i][j],inf);
            add(s,num[i][j]+(node<<1),ss[i][j]);//改成理科的额外收益
            ex+=ss[i][j];
            for(int dir=0;dir<4;dir++){
                int nx=i+dx[dir],ny=j+dy[dir];
                if(nx<1||nx>n||ny<1||ny>m)continue;
                add(num[i][j]+(node<<1),num[nx][ny],inf);
            }
        }
    }
}
inline void bfs(){//isap
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    queue<int>q;
    dep[t]=0;
    q.push(t);
    while(!q.empty()){
        register int now=q.front();q.pop();
        ++gap[dep[now]];
        for(register int i=fst[now];~i;i=e[i].nxt){
            if(e[i^1].f<=0||~dep[e[i].v])continue;
            dep[e[i].v]=dep[now]+1;
            q.push(e[i].v);
        }
    }
}
inline int dfs(register int now,int sum){//isap
    if(now==t||sum==0)return sum;
    register int ans=0;
    for(register int i=fst[now];~i;i=e[i].nxt){
        if(e[i].f<=0||dep[e[i].v]+1!=dep[now])continue;
        register int flow=dfs(e[i].v,min(e[i].f,sum));
        e[i].f-=flow;
        e[i^1].f+=flow;
        sum-=flow;
        ans+=flow;
        if(!sum)return ans;
    }
    if(!--gap[dep[now]])dep[s]=t+1;
    ++gap[++dep[now]];
    return ans;
}
inline int isap(){//isap
    maxflow=0;
    bfs();
    while(dep[s]<=t)maxflow+=dfs(s,inf);
    return maxflow;
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ar[i][j]=read();
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)sc[i][j]=read();
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)sa[i][j]=read();
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ss[i][j]=read();
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)num[i][j]=++node;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ans+=ar[i][j];
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ans+=sa[i][j];
    build();//建图
    isap();//isap网络流
    cout<<ans+ex-maxflow;//计算答案并输出
    return 0;
}