首页 > 代码库 > [BZOJ 2127]happiness（最小割）
[BZOJ 2127]happiness（最小割）
Description
高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。
Solution
和文理分科那道一样啊…1A
#include<iostream>#include<cstdlib>#include<cstdio>#include<cstring>#include<queue>#define INF 0x3f3f3f3fusing namespace std;int n,m,s,t,ans=0;int level[50005],head[50005],cnt=0;struct Node{ int next,to,cap;}Edges[500005];int read(){ int x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){ if(c==‘-‘)f=-1;c=getchar(); } while(c>=‘0‘&&c<=‘9‘){ x=x*10+c-‘0‘;c=getchar(); } return x*f;}void addedge(int u,int v,int c){ Edges[cnt].next=head[u]; head[u]=cnt; Edges[cnt].to=v; Edges[cnt++].cap=c;}void insert(int u,int v,int c){ addedge(u,v,c); addedge(v,u,0);}int pos(int x,int y){return (x-1)*m+y;}queue<int>q;bool bfs(){ memset(level,-1,sizeof(level)); q.push(s);level[s]=0; while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(level[v]==-1&&Edges[i].cap) level[v]=level[u]+1,q.push(v); } } if(level[t]==-1)return false; return true;}int dfs(int u,int f){ if(u==t)return f; int flow=0,d; for(int i=head[u];~i&&flow<f;i=Edges[i].next) { int v=Edges[i].to; if(level[v]==level[u]+1&&Edges[i].cap) { d=dfs(v,min(f-flow,Edges[i].cap)); flow+=d; Edges[i].cap-=d; Edges[i^1].cap+=d; } } if(!flow)level[u]=-1; return flow;}int main(){ memset(head,-1,sizeof(head)); n=read(),m=read(); s=0,t=n*m+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { int x=read(); insert(s,pos(i,j),x); ans+=x; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { int x=read(); insert(pos(i,j),t,x); ans+=x; } int num=t+1; for(int i=1;i<=n-1;i++) for(int j=1;j<=m;j++) { int x=read(); insert(s,num,x); insert(num,pos(i,j),INF); insert(num,pos(i+1,j),INF); ans+=x; num++; } for(int i=1;i<=n-1;i++) for(int j=1;j<=m;j++) { int x=read(); insert(num,t,x); insert(pos(i,j),num,INF); insert(pos(i+1,j),num,INF); ans+=x; num++; } for(int i=1;i<=n;i++) for(int j=1;j<=m-1;j++) { int x=read(); insert(s,num,x); insert(num,pos(i,j),INF); insert(num,pos(i,j+1),INF); ans+=x; num++; } for(int i=1;i<=n;i++) for(int j=1;j<=m-1;j++) { int x=read(); insert(num,t,x); insert(pos(i,j),num,INF); insert(pos(i,j+1),num,INF); ans+=x; num++; } int d; while(bfs()) { while(d=dfs(s,INF)) ans-=d; } printf("%d\n",ans); return 0;}
[BZOJ 2127]happiness（最小割）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。