bzoj3894文理分科

60 阅读 0 评论 40 点赞

我是靠谱客的博主壮观棒棒糖，最近开发中收集的这篇文章主要介绍bzoj3894文理分科，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目来源：http://www.lydsy.com/JudgeOnline/problem.php?id=3894

题目描述：文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠结过）

小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到：

1．如果第i行第j列的同学选择了文科，则他将获得art[i][j]的满意值，如果选择理科，将得到science[i][j]的满意值。

2．如果第i行第j列的同学选择了文科，并且他相邻（两个格子相邻当且仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开心，所以会增加same_art[i][j]的满意值。

3．如果第i行第j列的同学选择了理科，并且他相邻的同学全部选择了理科，则增加same_science[i][j]的满意值。

小P想知道，大家应该如何选择，才能使所有人的满意值之和最大。请告诉他这个最大值。

题解：这是一道最小割问题。我们记文科为源点S，理科为汇点T，从S向一个同学(i,j)连边权为art[i][j]的边，从该同学向T连一条边权为science[i][j]的边。对于每个同学，新建两个点，一个点从S向它连边，边权为same_art[i][j]，再从这个点连向该同学以及与该同学相邻同学的点，边权为inf，同理，从这些同学连向另一个新的点，边权为inf,再将该点与T连边，边权为same_science[i][j]。跑一遍最小割，答案为所有art[i][j]、science[i][j]、same_art[i][j]、same_science[i][j]的值之和与最小割的差。注意建边的方向！

代码：

  1 #include<queue> 
  2 #include<cmath> 
  3 #define inf 0x7fffffff
  4 using namespace std;
  5 #define p(i,j) ((i-1)*m+j)
  6 int read(){ 
  7     int x=0; 
  8     bool f=0; 
  9     char c; 
 10     for(;(c=getchar())<'0' || c>'9';f=c=='-'); 
 11     for(x=c-'0';(c=getchar())>='0' && c<='9';x=(x<<3)+(x<<1)+c-'0'); 
 12     return f?-x:x; 
 13 }
 14 int ans,tot=0;
 15 int n,m,s,t,cnt=1;
 16 int head[50005],level[50005],ite[50005],q[50010];
 17 struct edge{
 18     int to,next,cap;
 19 }e[1000010];
 20 const int dx[5]={0,0,-1,0,1};
 21 const int dy[5]={0,-1,0,1,0};
 22 void add(int u,int v,int c){ 
 23     e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].cap=c; 
 24     e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;e[cnt].cap=0; 
 25 }
 26 void bfs(){ 
 27     queue<int> q; 
 28     memset(level,-1,sizeof(level)); 
 29     level[s]=0;q.push(s); 
 30     while(!q.empty()){ 
 31         int x=q.front();q.pop(); 
 32         for(int i=head[x];i;i=e[i].next){ 
 33             if(e[i].cap>0 && level[e[i].to]<0){ 
 34                 level[e[i].to]=level[x]+1;q.push(e[i].to); 
 35             } 
 36         } 
 37     } 
 38 }
 39 int dfs(int v,int f){ 
 40     int used=0; 
 41     if(v==t)  return f; 
 42     for(int &i=ite[v];i;i=e[i].next){ 
 43         if(e[i].cap>0 && level[v]<level[e[i].to]){ 
 44             int w=dfs(e[i].to,min(f-used,e[i].cap)); 
 45             if(w>0){ 
 46                 e[i].cap-=w;e[i^1].cap+=w;used+=w; 
 47                 if(used==f)  return f; 
 48             } 
 49         } 
 50     } 
 51     return used; 
 52 }
 53 int dinic(){ 
 54     int flow=0; 
 55     for(;;){ 
 56         bfs(); 
 57         if(level[t]<0)  return flow; 
 58         memcpy(ite,head,sizeof(head)); 
 59         int d; 
 60         while((d=dfs(s,inf))>0)  flow+=d; 
 61     } 
 62 }
 63 int main(){
 64     n=read();m=read();t=3*n*m+1;
 65     int x,y,a;
 66     int i,j,k,l;
 67     for(int i=1;i<=n;i++)
 68         for(int j=1;j<=m;j++)
 69         {
 70             int x=read();
 71             add(0,p(i,j),x);
 72             tot+=x;
 73         }
 74     for(int i=1;i<=n;i++)
 75         for(int j=1;j<=m;j++)    
 76         {
 77             int x=read();
 78             add(p(i,j),t,x);
 79             tot+=x;
 80         }
 81     for(int i=1;i<=n;i++)
 82         for(int j=1;j<=m;j++)
 83         {
 84             int val=read();tot+=val;
 85             for(int k=0;k<5;k++)
 86             {
 87                 int x=dx[k]+i,y=dy[k]+j;
 88                 if(x>n||y>m||x<1||y<1)continue;
 89                 add(p(i,j)+n*m,p(x,y),inf);
 90             }
 91             add(0,p(i,j)+n*m,val);
 92         }
 93     for(int i=1;i<=n;i++)
 94         for(int j=1;j<=m;j++)
 95         {
 96             int val=read();tot+=val;
 97             for(int k=0;k<5;k++)
 98             {
 99                 int x=dx[k]+i,y=dy[k]+j;
100                 if(x>n||y>m||x<1||y<1)continue;
101                 add(p(x,y),p(i,j)+2*n*m,inf);
102             }
103             add(p(i,j)+2*n*m,t,val);
104         }
105     ans=dinic();
106     printf("%dn",tot-ans);
107     return 0;
108 }