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;
}

最新文章

  1. XML文件解析并利用SimpleAdapter将解析结果显示在Activity中
  2. DML以及DQL的使用方法
  3. Qt 之 自定义窗口标题栏(非常完善)
  4. Cocos2d-x 3.x项目创建
  5. Javac命令一次编译一个目录下的所有java文件
  6. meteor icons &amp; splash配置
  7. Android Studio 导入项目错误
  8. 自动生成makefile的脚本
  9. 清除div浮动的三种方式
  10. 我也谈javascript闭包的原理理解
  11. windows下查看端口占用情况及关闭相应的进程
  12. R+大地图时代︱ leaflet/leafletCN 动态、交互式绘制地图(遍地代码图)
  13. 编译GDAL支持MySQL
  14. 「Continuous_integration, CI」为什么要持续集成?
  15. Python------Mongodb操作
  16. LibreOJ 6277. 数列分块入门 2
  17. windows + hadoop + eclipse 过程记录
  18. win 下 nginx 与 php的配置
  19. HDU3861The King’s Problem
  20. Ubuntu 安装 PhpMyAdmin 图文教程

热门文章

  1. POJ Remmarguts&#39; Date
  2. [BZOJ2125]最短路[圆方树]
  3. 【亲测有效】Centos安装完成docker后启动docker报错docker: unrecognized service的两种解决方案
  4. Linux服务器更换主板后,网卡识别失败的处理方法
  5. Docker容器学习梳理 - 基础知识(2)
  6. 电梯调度系统(界面由C图形库编绘)
  7. Linux内核分析 第七周 可执行程序的装载
  8. 嵌入式linux教程
  9. BugPhobia进阶篇章:系统架构技术规格
  10. 2017BUAA软工个人作业Week1