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对每个人连art边权,每个人对T连sci边权。
棘手的就是处理文科和理科之间的关系。
考虑对每个人新建同文理点,向与其相邻的人(包括他自己)连INF的边(注意方向别反了),S向同文点连sameart边,同理点向T连samesci边。
(自己画一画图大概就能感受到它的正确性了)
跑一遍最大流最小割,然后用总边权减掉最大流即可。
#include<cstdio>
#include<cmath>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
typedef long long ll;
const int N=1e5+;
const int M=N*;
const int INF=1e9;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct node{
int nxt,to,w;
}edge[M];
int head[N],cnt=-,S,T;
inline void add(int u,int v,int w){
edge[++cnt].to=v;edge[cnt].w=w;edge[cnt].nxt=head[u];head[u]=cnt;
edge[++cnt].to=u;edge[cnt].w=;edge[cnt].nxt=head[v];head[v]=cnt;
}
int lev[N],cur[N],dui[N],a[][],b[][];
int da[][],db[][];
bool bfs(int m){
int r=;
for(int i=;i<=m;i++){
lev[i]=-;
cur[i]=head[i];
}
dui[]=S,lev[S]=;
int u,v;
for(int l=;l<=r;l++){
u=dui[l];
for(int e=head[u];e!=-;e=edge[e].nxt){
v=edge[e].to;
if(edge[e].w>&&lev[v]==-){
lev[v]=lev[u]+;
r++;
dui[r]=v;
if(v==T)return ;
}
}
}
return ;
}
int dinic(int u,int flow,int m){
if(u==m)return flow;
int res=,delta;
for(int &e=cur[u];e!=-;e=edge[e].nxt){
int v=edge[e].to;
if(edge[e].w>&&lev[u]<lev[v]){
delta=dinic(v,min(edge[e].w,flow-res),m);
if(delta>){
edge[e].w-=delta;
edge[e^].w+=delta;
res+=delta;
if(res==flow)break;
}
}
}
if(res!=flow)lev[u]=-;
return res;
}
int dx[]={,,,-,};
int dy[]={,,-,,};
int main(){
memset(head,-,sizeof(head));
int n=read(),m=read(),ans=;
S=n*m*+,T=S+;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
a[i][j]=read();
ans+=a[i][j];
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
b[i][j]=read();
ans+=b[i][j];
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
da[i][j]=read();
ans+=da[i][j];
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
db[i][j]=read();
ans+=db[i][j];
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
int now=(i-)*m+j;
add(S,now,a[i][j]);
add(now,T,b[i][j]);
add(S,now+n*m,da[i][j]);
add(now+*n*m,T,db[i][j]);
for(int k=;k<;k++){
int nx=i+dx[k],ny=j+dy[k];
if(nx<||nx>n||ny<||ny>m)continue;
int pre=(nx-)*m+ny;
add(now+n*m,pre,INF);
add(pre,now+*n*m,INF);
}
}
}
while(bfs(T))ans-=dinic(S,INF,T);
printf("%d\n",ans);
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者:luyouqi233。 +
+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++
最新文章
- How can i use iptables save on centos 7?
- c中的关键字、标识符、注释
- Jquery easyui Tree的简单使用
- Css - 文本溢出处理
- 使用VNC远程连接Windows Azure Linux虚拟机
- UVa 12627 (递归 计数 找规律) Erratic Expansion
- 简单实例一步一步帮你搞清楚MVC3中的路由以及区域
- NMAP扫描UDP123NTP端口详解
- html编码转换
- 我的Windows日常——Excel 打开.xls .xlsx 文件格式或文件扩展名无效
- Thunar 通过快捷键在当前文件夹打开终端
- python全栈开发 * 表格标签 表单标签 css 引入方式 * 180807
- js学习笔记--dom部分(一)
- 【Java入门提高篇】Day26 Java容器类详解(八)HashSet源码分析
- luogu P4161 [SCOI2009]游戏
- yield函数的理解
- eclipse中的maven build、maven clean、maven install和maven test的区别
- iOS-AFNetworking参数和多文件同时上传【多文件上传】
- java工程文件路径的问题
- (四)Qt实现自定义模型基于QAbstractTableModel (一般)