P4313 文理分科

思路

遇到这种利益冲突的最终利益最大化问题

考虑转化为最小割，使得损失的价值最小

相当于文科是S，理科是T，选出最小割就是确定损失代价最小的方案

然后就把S向每个点连一条cap=art[i][j]的边，每个点向T连一条cap=science[i][j]的边，再新建n*m个点表示同选文科的利益，然后S向每个新建点连一条cap=same_art[i][j]的边，然后再从新建点向每个点和它的相邻点向连一条cap=INF的边，然后同选立刻的收益同理新建点再向T连边，相邻点同理的向新建点连边

再跑出最小割即可

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <vector>

#include <queue>

using namespace std;

struct Edge{

    int u,v,cap,flow;

};

const int MAXN = 40100;

const int INF = 0x3f3f3f3f;

vector<Edge> edges;

vector<int> G[MAXN];

void addedge(int u,int v,int cap){

    edges.push_back((Edge){u,v,cap,0});

    edges.push_back((Edge){v,u,0,0});

    int cnt=edges.size();

    G[u].push_back(cnt-2);

    G[v].push_back(cnt-1);

}

int cur[MAXN],dep[MAXN],vis[MAXN],s,t;

int dfs(int x,int a){

    if(x==t||a==0)

        return a;

    int f,flow=0;

    for(int &i=cur[x];i<G[x].size();i++){

        Edge &e = edges[G[x][i]];

        if(dep[e.v]==dep[x]+1&&(f=dfs(e.v,min(e.cap-e.flow,a)))>0){

            flow+=f;

            e.flow+=f;

            edges[G[x][i]^1].flow-=f;

            a-=f;

            if(!a)

                break;

        }

    }

    return flow;

}

queue<int> q;

bool bfs(void){

    memset(vis,0,sizeof(vis));

    dep[s]=0;

    vis[s]=true;

    q.push(s);

    while(!q.empty()){

        int x=q.front();

        q.pop();

        for(int i=0;i<G[x].size();i++){

            Edge &e = edges[G[x][i]];

            if(e.cap>e.flow&&(!vis[e.v])){

                vis[e.v]=true;

                dep[e.v]=dep[x]+1;

                q.push(e.v);

            }

        }

    }

    return vis[t];

}

int dinic(void){

    int flow=0;

    while(bfs()){

            // printf("Not Re\n");

        memset(cur,0,sizeof(cur));

        flow+=dfs(s,INF);

    }

    return flow;

}

int n,m,same_wen[110][110],same_li[110][110],wen[110][110],li[110][110],sum=0;

const int mx[] = {0,0,1,-1,0},my[] ={0,1,0,0,-1};

int id(int x,int y,int idx=0){

    return (x-1)*m+y+idx*n*m;

}

int main(){

    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++){

            scanf("%d",&wen[i][j]);

            sum+=wen[i][j];

        }

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++){

            scanf("%d",&li[i][j]);

            sum+=li[i][j];

        }

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++){

            scanf("%d",&same_wen[i][j]);

            sum+=same_wen[i][j];

        }

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++){

            scanf("%d",&same_li[i][j]);

            sum+=same_li[i][j];

        }

    // printf("Not Re\n");

    s=MAXN-2;//wen

    t=MAXN-3;//li

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++){

            addedge(s,id(i,j),wen[i][j]);//wen

            addedge(id(i,j),t,li[i][j]);//li

        }

    for(int i=1;i<=n;i++)//shang

        for(int j=1;j<=m;j++){

            addedge(s,id(i,j,1),same_wen[i][j]);

            addedge(id(i,j,1),id(i,j),INF);

            if(i>1)

                addedge(id(i,j,1),id(i-1,j),INF);

            if(j>1)

                addedge(id(i,j,1),id(i,j-1),INF);

            if(i<n)

                addedge(id(i,j,1),id(i+1,j),INF);

            if(j<m)

                addedge(id(i,j,1),id(i,j+1),INF);

        }

    for(int i=1;i<=n;i++)//shang

        for(int j=1;j<=m;j++){

            addedge(id(i,j,2),t,same_li[i][j]);

            addedge(id(i,j),id(i,j,2),INF);

            if(i>1)

                addedge(id(i-1,j),id(i,j,2),INF);

            if(j>1)

                addedge(id(i,j-1),id(i,j,2),INF);

            if(i<n)

                addedge(id(i+1,j),id(i,j,2),INF);

            if(j<m)

                addedge(id(i,j+1),id(i,j,2),INF);

        }

    // printf("Not Re\n");

    printf("%d\n",sum-dinic());

    return 0;

}