【bzoj3438】 小M的作物
2024-10-19 02:26:24
http://www.lydsy.com/JudgeOnline/problem.php?id=3438 (题目链接)
题意
$n$种作物,每种可以种在A田也可以种在B田,两种种植方法有不同的收益。$m$个组合,如果一个组合中的作物种在同一块田地,那么可以获得额外的收益。问最大收益。
Solution
最小割。
源点向作物连边,容量$a[i]$,作物向汇点连边,容量$b[i]$。
$m$组点,每组两个。第一个由源点连向它,再连向组合中的作物;第二个连向汇点,由组合中的作物连过来。
细节
mdzz这数组到底要开多大= =
代码
// bzoj3438
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define inf (1ll<<30)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std; const int maxn=5010,maxm=1000010;
int head[maxn],a[maxn],b[maxn],n,m,S,T,cnt=1;
LL ans;
struct edge {int to,next,w;}e[maxm<<1]; void link(int u,int v,int w) {
e[++cnt]=(edge){v,head[u],w};head[u]=cnt;
e[++cnt]=(edge){u,head[v],0};head[v]=cnt;
}
namespace Dinic {
int d[maxn];
bool bfs() {
for (int i=S;i<=T;i++) d[i]=-1;
queue<int> q;q.push(S);d[S]=0;
while (!q.empty()) {
int x=q.front();q.pop();
for (int i=head[x];i;i=e[i].next)
if (e[i].w && d[e[i].to]<0) d[e[i].to]=d[x]+1,q.push(e[i].to);
}
return d[T]>0;
}
int dfs(int x,int f) {
if (x==T || f==0) return f;
int w,used=0;
for (int i=head[x];i;i=e[i].next) if (d[e[i].to]==d[x]+1 && e[i].w) {
w=dfs(e[i].to,min(e[i].w,f-used));
used+=w;e[i].w-=w;e[i^1].w+=w;
if (used==f) return used;
}
if (!used) d[x]=-1;
return used;
}
LL main() {
LL flow=0;
while (bfs()) flow+=dfs(S,inf);
return flow;
}
} int main() {
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]),ans+=a[i];
for (int i=1;i<=n;i++) scanf("%d",&b[i]),ans+=b[i];
scanf("%d",&m);
S=0,T=n+2*m+1;
for (int i=1;i<=n;i++) link(S,i,a[i]),link(i,T,b[i]);
for (int k,x,y,t,i=1;i<=m;i++) {
scanf("%d%d%d",&k,&x,&y);
ans+=x+y;
link(S,i+n,x);link(i+n+m,T,y);
for (int j=1;j<=k;j++) scanf("%d",&t),link(i+n,t,inf),link(t,i+n+m,inf);
}
printf("%lld",ans-Dinic::main());
return 0;
}
最新文章
- XML文件解析并利用SimpleAdapter将解析结果显示在Activity中
- DML以及DQL的使用方法
- Qt 之 自定义窗口标题栏(非常完善)
- Cocos2d-x 3.x项目创建
- Javac命令一次编译一个目录下的所有java文件
- meteor icons &; splash配置
- Android Studio 导入项目错误
- 自动生成makefile的脚本
- 清除div浮动的三种方式
- 我也谈javascript闭包的原理理解
- windows下查看端口占用情况及关闭相应的进程
- R+大地图时代︱ leaflet/leafletCN 动态、交互式绘制地图(遍地代码图)
- 编译GDAL支持MySQL
- 「Continuous_integration, CI」为什么要持续集成?
- Python------Mongodb操作
- LibreOJ 6277. 数列分块入门 2
- windows + hadoop + eclipse 过程记录
- win 下 nginx 与 php的配置
- HDU3861The King’s Problem
- Ubuntu 安装 PhpMyAdmin 图文教程
热门文章
- POJ Remmarguts&#39; Date
- [BZOJ2125]最短路[圆方树]
- 【亲测有效】Centos安装完成docker后启动docker报错docker: unrecognized service的两种解决方案
- Linux服务器更换主板后,网卡识别失败的处理方法
- Docker容器学习梳理 - 基础知识(2)
- 电梯调度系统(界面由C图形库编绘)
- Linux内核分析 第七周 可执行程序的装载
- 嵌入式linux教程
- BugPhobia进阶篇章:系统架构技术规格
- 2017BUAA软工个人作业Week1