P4313 文理分科

题意简述

有(n imes m)个座位，每个座位上的同学可以选择文科和理科。如果((i,j))上的同学选文科，答案加(art_{i,j})，如果选理科，答案加(sci_{i,j})。如果一个位置和其上、下、左、右（不包括没人的地方）都选文或理，则答案再加上(sameart_{i,j})或(samesci_{i,j})，求最大答案。

简单口胡

这题用最小割，因为这种两者选择的题目，显然是先把和求出来，在求出最小割减掉。
考虑建图，首先肯定是先连所有的((S,(i,j),art_{i,j}))和(((i,j),T,sci_{i,j}))
然后((S,(i,j),sameart_{i,j}))和(((i,j),T,samesci_{i,j}))
最小割转成最大流，没了。
难度主要在建边。

# include <bits/stdc++.h>

using namespace std;

const int N = 30100;
const int M = 240005;

int n,m;
int art[105][105];
int sci[105][105];
int same_art[105][105];
int same_sci[105][105];
int cur[N];

struct edge
{
    int u,v,w;
    int nxt;
    edge() {}
    edge(int _u,int _v,int _w) : u(_u),v(_v),w(_w) {}
}E[M << 1];

int Head[N];
int tot = 1;
int dep[N];

void add(int u,int v,int w)
{
    E[++tot] = edge(u,v,w);
    E[tot].nxt = Head[u];
    Head[u] = tot;
    E[++tot] = edge(v,u,0);
    E[tot].nxt = Head[v];
    Head[v] = tot;
    return;
}

int id(int x,int y)
{
    return (x - 1) * m + y;
}

int s,t;

bool bfs(void)
{
    memset(dep,0,sizeof(dep));
    dep[s] = 1;
    queue <int> q;
    q.push(s);
    while(!q.empty())
    {
        int x = q.front();q.pop();
        for(int i = Head[x]; i ; i = E[i].nxt)
        {
            int v = E[i].v;
            if(!dep[v] && E[i].w)
            {
                dep[v] = dep[x] + 1;
                q.push(v);
            }
        }
    }
    return dep[t] > 0;
}

int dfs(int x,int a)
{
    int sum = 0;
    if(x == t || a == 0) return a;
    for(int i = cur[x]; i ; i = E[i].nxt)
    {
        int v = E[i].v;
        if(dep[v] == dep[x] + 1 && E[i].w)
        {
            int tmp = dfs(v,min(a - sum,E[i].w));
            sum += tmp;
            E[i].w -= tmp;
            E[i xor 1].w += tmp;
        }
    }
    return sum;
}

int main(void)
{
    scanf("%d%d",&n,&m);
    int SUM = 0;
    s = 0,t = n * m + 1;
    int cnt = t;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            scanf("%d",&art[i][j]);
            add(s,id(i,j),art[i][j]);
            SUM += art[i][j];
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            scanf("%d",&sci[i][j]);
            add(id(i,j),t,sci[i][j]);  
            SUM += sci[i][j];
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            scanf("%d",&same_art[i][j]);
            ++cnt;
            add(s,cnt,same_art[i][j]);
            add(cnt,id(i,j),2e9 + 7);
            SUM += same_art[i][j];
            if(i - 1 >= 1) add(cnt,id(i - 1,j),2e9 + 7);
            if(i + 1 <= n) add(cnt,id(i + 1,j),2e9 + 7);
            if(j - 1 >= 1) add(cnt,id(i,j - 1),2e9 + 7);
            if(j + 1 <= m) add(cnt,id(i,j + 1),2e9 + 7);
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            scanf("%d",&same_sci[i][j]);
            ++cnt;
            add(cnt,t,same_sci[i][j]);
            add(id(i,j),cnt,2e9 + 7);
            SUM += same_sci[i][j];
            if(i - 1 >= 1) add(id(i - 1,j),cnt,2e9 + 7);
            if(i + 1 <= n) add(id(i + 1,j),cnt,2e9 + 7);
            if(j - 1 >= 1) add(id(i,j - 1),cnt,2e9 + 7);
            if(j + 1 <= m) add(id(i,j + 1),cnt,2e9 + 7);
        }
    }
    int flow = 0;
    while(bfs()) 
    {
        for(int i = 0; i <= cnt; i++) cur[i] = Head[i];
        flow += dfs(s,2e9);
    }
    printf("%d
",SUM - flow);
    return 0;
}