【bzoj3894】文理分科 网路流
2024-08-27 15:16:56
【bzoj3894】文理分科
2015年3月25日3,4002
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 58 13 15 4
11 3 8 11
11 18 6 51 2 3 4
4 2 3 2
3 1 0 4
13 2 4 13
7 13 8 12
18 17 0 58 13 15 4
11 3 8 11
11 18 6 51 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
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue> #define inf 1000000007
#define N 30007
#define M 1000007
using namespace std;
const int xx[]={,,-,,};
const int yy[]={,,,,-};
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if (ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,m,S,T,ans;
int cnt=,hed[N],cur[N],nxt[M],rea[M],val[M];
int dis[N]; void add(int u,int v,int w)
{
nxt[++cnt]=hed[u];
hed[u]=cnt;
rea[cnt]=v;
val[cnt]=w;
}
void add_two_edge(int u,int v,int w)
{
add(u,v,w),add(v,u,);
}
bool bfs()
{
for (int i=S;i<=T;i++)dis[i]=-;
dis[S]=;queue<int>q;q.push(S);
while(!q.empty())
{
int u=q.front();q.pop();
for (int i=hed[u];i!=-;i=nxt[i])
{
int v=rea[i],fee=val[i];
if (dis[v]!=-||fee==)continue;
dis[v]=dis[u]+;
if (v==T)return ;
q.push(v);
}
}
return ;
}
int dfs(int u,int MX)
{
if (u==T||MX==) return MX;
int res=;
for (int i=cur[u];i!=-;i=nxt[i])
{
int v=rea[i],fee=val[i];
if (dis[v]!=dis[u]+)continue;
int x=dfs(v,min(MX,fee));
cur[u]=i,res+=x,MX-=x;
val[i]-=x,val[i^]+=x;
if (!MX)break;
}
if (!res) dis[u]=-;
return res;
}
int dinic()
{
int res=;
while(bfs())
{
// cout<<1<<endl;
for (int i=S;i<=T;i++)cur[i]=hed[i];
res+=dfs(S,inf);
}
return res;
}
int main()
{
memset(hed,-,sizeof(hed));
n=read(),m=read(),S=,T=n*m*+;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
{
int x=read();ans+=x;
add_two_edge(S,(i-)*m+j,x);
}
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
{
int x=read();ans+=x;
add_two_edge((i-)*m+j,T,x);
}
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
{
int x=read();ans+=x;
for (int k=;k<;k++)
{
int lx=i+xx[k],ly=j+yy[k];
if (lx<||lx>n||ly<||ly>m)continue;
add_two_edge((i-)*m+j+n*m,(lx-)*m+ly,inf);
}
add_two_edge(S,(i-)*m+j+n*m,x);
}
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
{
int x=read();ans+=x;
for (int k=;k<;k++)
{
int lx=i+xx[k],ly=j+yy[k];
if (lx<||lx>n||ly<||ly>m)continue;
add_two_edge((lx-)*m+ly,(i-)*m+j+*n*m,inf);
}
add_two_edge((i-)*m+j+*n*m,T,x);
}
ans-=dinic();
printf("%d\n",ans);
}
最新文章
- ORACLE 迁移MYSQL 随笔
- C#程序使用SQLite数据库
- STM32——外部中断EXIT实现
- Azure China (4) 管理Azure China Storage Account
- 烂泥:vsftpd单用户多目录配置
- thinkphp 3.2视图里添加URL参数 实例
- 通过sqlserver日志恢复误删除的数据
- Dev gridview新增一行自动获得焦点并打开编辑模式
- 迪米特法则(LoD),即最少知识原则
- 清空FORM表单的几种方式 Reset 重加载
- Android 跨应用调用Activity及Service
- 10--动作系统(四)动作类中的reverse方法
- 使用docker搭建kafka环境
- Beta Scrum Day 1
- 帆软报表(finereport)间格运算常用公式
- codeforces / project Euler 泛做
- 使用readAsDataURL方法预览图片
- 基数排序模板(基数排序,C++模板)
- 物联网架构成长之路(25)-Docker构建项目用到的镜像1
- eclipse工具类及插件(Eclipse超好用的插件推荐)