思路

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

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

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

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

再跑出最小割即可

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;struct Edge{    int u,v,cap,flow;};const int MAXN = 40100;const int INF = 0x3f3f3f3f;vector
         
           edges;vector
          
            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
           
            0){ flow+=f; e.flow+=f; edges[G[x][i]^1].flow-=f; a-=f; if(!a) break; } } return flow;}queue
            
              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
             
              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
              
               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