bzoj3894 文理分科

bzoj3894 文理分科

​​ Description 文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠 结过） 小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想知道，大家应该如何选择，才能使所有人的满意值之和最大。请 告诉他这个最大值。

Input

第一行为两个正整数：n，m 接下来n术m个整数，表示art[i][j]； 接下来n术m个整数．表示science[i][j]； 接下来n术m个整数，表示same_art[i][j]；

Output

输出为一个整数，表示最大的满意值之和

Sample Input 3 4 13 2 4 13 7 13 8 12 18 17 0 5

8 13 15 4 11 3 8 11 11 18 6 5

1 2 3 4 4 2 3 2 3 1 0 4

3 2 3 2 0 2 2 1 0 2 4 4 Sample Output 152 HINT 样例说明

1表示选择文科，0表示选择理科，方案如下：

1 0 0 1

0 1 0 0

1 0 0 0

N,M<=100,读入数据均<=500 这题的建图非常有意思 以我的个人能力只能想到一半吧 我多菜啊 大概就是有点像bzoj3132 然后再给他拆个点就好 首先呢 我先把每个人拆成三个点 一个代表本身的点 一个代表文理分科的点 首先呢就是每个点从源连向这个点连文科的值 这个点向汇连理科的值 那么我割去哪个代表我就没选哪个呗 然后 假设我文科都选的那个点叫p1吧 理科都选的那个点叫p2 那么有如下的性质 我从源向p1连 如果他附近都选文的代价 然后他向自己 还有周边的点都连inf的边 这样的话 为了保证这条边的存在我不得不把和我有关的理科的边都割去 从我p2向汇连容量为都选理科的代价 然后从我自己向p2连inf 的边 从 任意有关联的点向p2连inf的边 那么同理 如果想保留这个点的话 必须把有关的还有自己的文科边都割去才行 那么求一下原图的最小割用总和减一减即可了呢

#include#include#include#include#define N 33000#define inf 0x3f3f3f3fusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}int dx[]={0,1,-1,0},dy[]={1,0,0,-1},id[110][110],id1[110][110],id2[110][110];int h[N],level[N],num=1,T,cur[N],n,m;struct node{ int y,z,next;}data[N*10];inline void insert1(int x,int y,int z){ data[++num].y=y;data[num].z=z;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].z=0;data[num].next=h[y];h[y]=num;}inline bool bfs(){ queueq;q.push(0);memset(level,0,sizeof(level));level[0]=1; while(!q.empty()){ int x=q.front();q.pop(); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if(level[y]||!z) continue; level[y]=level[x]+1;if (y==T) return 1;q.push(y); } }return 0;}inline int dfs(int x,int s){ if (x==T) return s;int ss=s; for (int &i=cur[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if(level[x]+1==level[y]&&z){ int xx=dfs(y,min(z,s));if (!xx) level[y]=0; s-=xx;data[i].z-=xx;data[i^1].z+=xx;if (!s) return ss; } }return ss-s;}int main(){ freopen("bzoj3894.in","r",stdin); n=read();m=read();int tot=0,sum=0; for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) id[i][j]=++tot,id1[i][j]=++tot,id2[i][j]=++tot;T=tot+1; for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) {int tmp=read();sum+=tmp;insert1(0,id[i][j],tmp);} for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) {int tmp=read();sum+=tmp;insert1(id[i][j],T,tmp);} for (int i=1;i<=n;++i){ for (int j=1;j<=m;++j){ int tmp=read();sum+=tmp; insert1(0,id1[i][j],tmp);insert1(id1[i][j],id[i][j],inf); for (int k=0;k<4;++k){ int x1=i+dx[k],y1=j+dy[k]; if (x1<1||x1>n||y1<1||y1>m) continue; insert1(id1[i][j],id[x1][y1],inf); } } } for (int i=1;i<=n;++i){ for (int j=1;j<=m;++j){ int tmp=read();sum+=tmp; insert1(id2[i][j],T,tmp);insert1(id[i][j],id2[i][j],inf); for (int k=0;k<4;++k){ int x1=i+dx[k],y1=j+dy[k]; if (x1<1||x1>n||y1<1||y1>m) continue; insert1(id[x1][y1],id2[i][j],inf); } } }int ans=0;while(bfs()) memcpy(cur,h,sizeof(h)),ans+=dfs(0,inf); printf("%d",sum-ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。