题目大意:将作物种在A,B两地,对于每种作物,种A,B分别有不同的收益,对于一些特殊的作物集合,共同种到A,B集合分别有一些额外收益。求最大收益。

题解:最小割,S向i连容量为$a_i$的边,i向T连容量为$b_i$,对于每个集合,建两个大点,把每组内的点与其连接,容量为inf,两个大点分别与原点或汇点相连,容量为$c_{i1}$和$c_{i2}$

卡点:1.把inf的边设成了双向边

C++ Code:

#include <cstdio>
#include <cstring>
#define N 4010
#define M 2003010
using namespace std;
const int inf = 0x3f3f3f3f;
int st, ed , sum;
int d[N], q[N], h, t;
int n, m, k, o, c1, c2;
int cnt = 2, head[N];
struct Edge {
int to, nxt, w;
}e[M << 1]; inline int min(int a, int b) {return a < b ? a : b;}
void addE(int a, int b, int c){
e[cnt] = (Edge) {b, head[a], c}; head[a] = cnt;
e[cnt ^ 1] = (Edge) {a, head[b], 0}; head[b] = cnt ^ 1;
cnt += 2;
}
void addE_(int a, int b, int c){
e[cnt] = (Edge) {b, head[a], c}; head[a] = cnt;
e[cnt ^ 1] = (Edge) {a, head[b], c}; head[b] = cnt ^ 1;
cnt += 2;
}
bool bfs() {
memset(d, 0, sizeof d);
d[q[h = t = 0] = st] = 1;
while (h <= t) {
int u = q[h++];
if (u == ed) return true;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if ((!d[v]) && (e[i].w)){
d[v] = d[u] + 1;
q[++t] = v;
}
}
}
return d[ed];
}
int dfs(int u, int low) {
if ((u == ed) || (low <= 0)) return low;
int res = 0;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if ((d[v] == d[u] + 1) && (e[i].w)){
int w = dfs(v, min(e[i].w, low - res));
e[i].w -= w;
e[i ^ 1].w += w;
res += w;
if (res == low) return res;
}
}
if (!res) d[u] = -1;
return res;
}
void dinic() {
int ans = 0;
while (bfs()) {
ans += dfs(st, inf);
// printf("%d\n", ans);
}
printf("%d\n", sum - ans);
}
int main() {
scanf("%d", &n);
st = 0; ed = 4009;
for (int i = 1; i <= n; i++) {scanf("%d", &o); addE(st, i, o); sum += o;}
for (int i = 1; i <= n; i++) {scanf("%d", &o); addE(i, ed, o); sum += o;}
scanf("%d", &m);
for (int l = 1; l <= m; l++) {
scanf("%d%d%d", &k, &c1, &c2); sum += c1 + c2;
addE(st, l + n, c1);
addE(l + n + m, ed, c2);
for (int i = 1; i <= k; i++) {scanf("%d", &o); addE(l + n, o, inf); addE(o, l + n + m, inf);}
}
dinic();
return 0;
}

  

最新文章

  1. MyBatis6:MyBatis集成Spring事物管理(下篇)
  2. BZOJ AC800纪念
  3. oracle常用系统表
  4. GridView里做页面的链接
  5. bzoj4514: [Sdoi2016]数字配对--费用流
  6. URAL 1671 Anansi&#39;s Cobweb (并查集)
  7. 论文阅读之 DECOLOR: Moving Object Detection by Detecting Contiguous Outliers in the Low-Rank Representation
  8. [Java] java中的异常处理
  9. 创业草堂之二十二:创业公司C类官员的职位说明书
  10. MySQL性能调优与架构设计读书笔记
  11. 使用django+celery+RabbitMQ实现异步执行
  12. Swift 制作一个新闻通知中心插件1
  13. Android小应用-----画画板
  14. VS2017 Cordova 出现错误 @ionic/app-scripts 未安装
  15. SpriteBuilder中锚点的一般用法
  16. iOS 封装SDK以及封装时bundle文件的处理
  17. cf860E Arkady and A Nobody-men (树剖)
  18. exportfs命令
  19. 再学Java 之 interface的成员变量
  20. oracl数据库中的substr()函数的用法

热门文章

  1. PHP单引号和双引号的区别。
  2. python 摘要算法
  3. js onsubmit和return false的关系
  4. Ubunut18.04与Windows传输文件的方式
  5. flask的模板
  6. 怎么修复网站漏洞 骑士cms的漏洞修复方案
  7. go学习笔记-程序测试
  8. 分支push不上去的问题
  9. VS中的一些标记
  10. [bzoj1359][Baltic2009]Candy