首页 > 代码库 > BZOJ 2127: happiness(最小割解决集合划分)
BZOJ 2127: happiness(最小割解决集合划分)
Submit: 2350 Solved: 1138
[Submit][Status][Discuss]
Description
高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。
Input
第一行两个正整数n，m。接下来是六个矩阵第一个矩阵为n行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学选择文科获得的喜悦值。第二个矩阵为n行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学选择理科获得的喜悦值。第三个矩阵为n-1行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i+1行第j列的同学同时选择文科获得的额外喜悦值。第四个矩阵为n-1行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i+1行第j列的同学同时选择理科获得的额外喜悦值。第五个矩阵为n行m-1列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i行第j+1列的同学同时选择文科获得的额外喜悦值。第六个矩阵为n行m-1列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i行第j+1列的同学同时选择理科获得的额外喜悦值。
Output
输出一个整数，表示喜悦值总和的最大值
Sample Input
1 2
1 1
100 110
1
1000
1 1
100 110
1
1000
Sample Output
1210
【样例说明】
两人都选理，则获得100+110+1000的喜悦值。
【数据规模】
对于100%以内的数据，n,m<=100 所有喜悦值均为小于等于5000的非负整数
【样例说明】
两人都选理，则获得100+110+1000的喜悦值。
【数据规模】
对于100%以内的数据，n,m<=100 所有喜悦值均为小于等于5000的非负整数
HINT
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 using namespace std; 7 const int MAXN=200001; 8 const int INF = 1e8; 9 inline void read(int &n) 10 { 11 char c=‘+‘;int x=0;bool flag=0; 12 while(c<‘0‘||c>‘9‘){c=getchar();if(c==‘-‘)flag=1;} 13 while(c>=‘0‘&&c<=‘9‘){x=x*10+c-48;c=getchar();} 14 n=flag==1?-x:x; 15 } 16 int n,m,s,t; 17 struct node 18 { 19 int u,v,flow,nxt; 20 }edge[MAXN]; 21 int head[MAXN]; 22 int cur[MAXN]; 23 int num=0; 24 int deep[MAXN]; 25 int tot=0; 26 void add_edge(int x,int y,int z) 27 { 28 edge[num].u=x; 29 edge[num].v=y; 30 edge[num].flow=z; 31 edge[num].nxt=head[x]; 32 head[x]=num++; 33 } 34 void add(int x,int y,int z) 35 { 36 add_edge(x,y,z); 37 add_edge(y,x,0); 38 } 39 bool BFS() 40 { 41 memset(deep,0,sizeof(deep)); 42 deep[s]=1; 43 queue<int>q; 44 q.push(s); 45 while(q.size()!=0) 46 { 47 int p=q.front(); 48 q.pop(); 49 for(int i=head[p];i!=-1;i=edge[i].nxt) 50 if(!deep[edge[i].v]&&edge[i].flow) 51 deep[edge[i].v]=deep[edge[i].u]+1, 52 q.push(edge[i].v); 53 } 54 return deep[t]; 55 56 } 57 int DFS(int now,int nowflow) 58 { 59 if(now==t||nowflow<=0) 60 return nowflow; 61 int totflow=0; 62 for(int &i=cur[now];i!=-1;i=edge[i].nxt) 63 { 64 if(deep[edge[i].v]==deep[edge[i].u]+1&&edge[i].flow) 65 { 66 int canflow=DFS(edge[i].v,min(nowflow,edge[i].flow)); 67 edge[i].flow-=canflow; 68 edge[i^1].flow+=canflow; 69 totflow+=canflow; 70 nowflow-=canflow; 71 if(nowflow<=0) 72 break; 73 } 74 75 } 76 return totflow; 77 } 78 void Dinic() 79 { 80 int ans=0; 81 while(BFS()) 82 { 83 memcpy(cur,head,MAXN); 84 ans+=DFS(s,1e8); 85 } 86 printf("%d",tot-(ans>>1)); 87 } 88 int a[101][101]; 89 int b[101][101]; 90 int mark[101][101]; 91 int main() 92 { 93 int n,m; 94 read(n);read(m); 95 s=0;t=10001; 96 memset(head,-1,sizeof(head)); 97 for(int i=1;i<=n;i++) 98 for(int j=1;j<=m;j++) 99 cin>>a[i][j],tot+=a[i][j],a[i][j]<<=1;100 for(int i=1;i<=n;i++)101 for(int j=1;j<=m;j++)102 cin>>b[i][j],tot+=b[i][j],b[i][j]<<=1;103 for(int i=1;i<=n;i++)104 for(int j=1;j<=m;j++)105 mark[i][j]=((i-1)*m+j);106 for(int i=1;i<=n-1;i++)107 for(int j=1;j<=m;j++)108 {109 int p;cin>>p;tot+=p;110 a[i][j]+=p,a[i+1][j]+=p;111 add_edge(mark[i][j],mark[i+1][j],p);112 add_edge(mark[i+1][j],mark[i][j],p);113 }114 for(int i=1;i<=n-1;i++)115 for(int j=1;j<=m;j++)116 {117 int p;cin>>p;tot+=p;118 b[i][j]+=p,b[i+1][j]+=p;119 add_edge(mark[i][j],mark[i+1][j],p);120 add_edge(mark[i+1][j],mark[i][j],p);121 }122 for(int i=1;i<=n;i++)123 for(int j=1;j<=m-1;j++)124 {125 int p;cin>>p;tot+=p;126 a[i][j]+=p,a[i][j+1]+=p;127 add_edge(mark[i][j],mark[i][j+1],p);128 add_edge(mark[i][j+1],mark[i][j],p);129 }130 for(int i=1;i<=n;i++)131 for(int j=1;j<=m-1;j++)132 {133 int p;cin>>p;tot+=p;134 b[i][j]+=p,b[i][j+1]+=p;135 add_edge(mark[i][j],mark[i][j+1],p);136 add_edge(mark[i][j+1],mark[i][j],p);137 }138 for(int i=1;i<=n;i++)139 for(int j=1;j<=m;j++)140 {141 add(0,mark[i][j],a[i][j]);142 add(mark[i][j],t,b[i][j]);143 }144 Dinic();145 return 0;146 }
BZOJ 2127: happiness(最小割解决集合划分)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。