[P4313] 文理分科 - 最小割

Description

班级可以用一个 \(n \times m\) 的矩阵进行描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。如果第 \(i\) 行第 \(j\) 列的同学选择了文科，则他将获得 \(art[i][j]\) 的满意值，如果选择理科，将得到 \(science[i][j]\) 的满意值。如果第 \(i\) 行第 \(j\) 列的同学选择了文科，并且他相邻（两个格子相邻当且仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开心，所以会增加 \(sameart[i][j]\)的满意值。如果第 \(i\) 行第 \(j\) 列的同学选择了理科，并且他相邻的同学全部选择了理科，则增加 \(samescience[i][j]\)的满意值。使所有人的满意值之和最大。

Solution

考虑最小割，割掉的是不选的

S 向 i 连边，边权为 art[i]，如果割了，则表示这个人选了理科

i 向 T 连边，边权为 sci[i]，如果割了，则代表这个人选了文科

对于每一个相邻区域，新建一个点 p

S 向 p 连边，边权为 sameart[i]，如果没割掉，则代表这些人全选了文科，p 向所有被该区域包含的点连边，边权为 inf

p 向 T 连边，边权为 samesci[i]，如果没割掉，则代表这些人全选了理科，所有被该区域包含的点向 p 连边，边权为 inf

#include <bits/stdc++.h>
using namespace std;

const int di[5]={0,0,0,1,-1};
const int dj[5]={0,1,-1,0,0};

#define int long long
namespace flow {

const int maxn = 200005;
const int inf = 1e+9;

int dis[maxn], ans, cnt = 1, s, t, pre[maxn * 10], nxt[maxn * 10], h[maxn], v[maxn * 10];
std::queue<int> q;
void make(int x, int y, int z) {
    pre[++cnt] = y, nxt[cnt] = h[x], h[x] = cnt, v[cnt] = z;
    pre[++cnt] = x, nxt[cnt] = h[y], h[y] = cnt;
}
bool bfs() {
    memset(dis, 0, sizeof dis);
    q.push(s), dis[s] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = h[x]; i; i = nxt[i])
            if (!dis[pre[i]] && v[i])
                dis[pre[i]] = dis[x] + 1, q.push(pre[i]);
    }
    return dis[t];
}
int dfs(int x, int flow) {
    if (x == t || !flow)
        return flow;
    int f = flow;
    for (int i = h[x]; i; i = nxt[i])
        if (v[i] && dis[pre[i]] > dis[x]) {
            int y = dfs(pre[i], min(v[i], f));
            f -= y, v[i] -= y, v[i ^ 1] += y;
            if (!f)
                return flow;
        }
    if (f == flow)
        dis[x] = -1;
    return flow - f;
}
int solve(int _s,int _t) {
    s=_s;
    t=_t;
    ans = 0;
    for (; bfs(); ans += dfs(s, inf));
    return ans;
}
}

using flow::make;

const int N = 105;
const int inf = 1e9;
int n,m,t1,t2,t3,art[N][N],sci[N][N],sameart[N][N],samesci[N][N];

int id(int i,int j) {
    return i*m-m+j;
}

bool ok(int i,int j) {
    return i>0 && j>0 && i<=n && j<=m;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int ind=n*m+2;
    int s=ind-1,t=ind,sum=0;

    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin>>art[i][j];
            sum+=art[i][j];
            make(s,id(i,j),art[i][j]);
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin>>sci[i][j];
            sum+=sci[i][j];
            make(id(i,j),t,sci[i][j]);
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            ++ind;
            cin>>sameart[i][j];
            sum+=sameart[i][j];
            make(s,ind,sameart[i][j]);
            for(int k=0;k<=4;k++) {
                int ni=i+di[k],nj=j+dj[k];
                if(ok(ni,nj)) {
                    make(ind,id(ni,nj),inf);
                }
            }
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            ++ind;
            cin>>samesci[i][j];
            sum+=samesci[i][j];
            make(ind,t,samesci[i][j]);
            for(int k=0;k<=4;k++) {
                int ni=i+di[k],nj=j+dj[k];
                if(ok(ni,nj)) {
                    make(id(ni,nj),ind,inf);
                }
            }
        }
    }
    cout<<sum-flow::solve(s,t);

}

[P4313] 文理分科 - 最小割

原文：https://www.cnblogs.com/mollnn/p/13159509.html