最裸的最大流,没啥好说的。。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int, int> using namespace std; const int N = + ;
const int M = 1e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 +; int n, m, tot, S, T, sum, head[N << ], level[N << ], a[N << ], b[N << ]; struct node {
int u, v, w, nx;
} edge[M << ]; void add(int u, int v, int w) {
edge[tot].u = u; edge[tot].v = v; edge[tot].w = w;
edge[tot].nx = head[u]; head[u] = tot++;
} bool bfs() {
memset(level, , sizeof(level));
queue<int> que;
level[S] = ; que.push(S); while(!que.empty()) {
int u = que.front(); que.pop();
if(u == T) return true; for(int i = head[u]; ~i; i = edge[i].nx) {
int v = edge[i].v;
if(level[v] || edge[i].w <= ) continue;
level[v] = level[u] + ;
que.push(v);
}
}
return false;
} int dfs(int u, int p) {
if(u == T) return p;
int ret = ;
for(int i = head[u]; ~i; i = edge[i].nx) {
int v = edge[i].v, w = edge[i].w;
if(level[v] != level[u] + || w <= ) continue;
int f = dfs(v, min(p - ret, w));
ret += f;
edge[i].w -= f;
edge[i ^ ].w += f;
if(ret == p) break;
}
if(!ret) level[u] = ;
return ret;
} int Dinic() { int ans = ;
while(bfs()) ans += dfs(S, inf);
return ans;
} void init() {
tot = ;
sum = ;
memset(head, -, sizeof(head));
} int main(){
int cas; scanf("%d", &cas);
while(cas--) {
init();
scanf("%d%d", &n, &m); S = , T = n + m + ;
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
add(i, T, a[i]);
add(T, i, );
sum += a[i];
} for(int i = ; i <= m; i++) {
scanf("%d", &b[i]);
add(S, i + n, b[i]);
add(i + n, S, );
} for(int i = ; i <= m; i++) {
int k; scanf("%d", &k);
for(int j = ; j <= k; j++) {
int id; scanf("%d", &id);
add(i + n, id, inf);
add(id, i + n, );
}
} int ans = Dinic();
printf("%d\n", sum - ans);
}
return ;
} /*
*/

最新文章

  1. 利用AOP写2PC框架(一)
  2. Android布局---相对布局
  3. CentOS7安装配置FTP服务器
  4. ECshop 二次开发模板教程4
  5. html5实现渐变效果
  6. [Android]Fragment源代码分析(二) 状态
  7. Heritrix源码分析(十五)
  8. HTML动画(难点)
  9. JSP中的include有哪些?有什么区别?
  10. CentOS 7 安装Graphite
  11. [USACO08JAN]haybale猜测Haybale Guessing
  12. 正则与python的re模块
  13. Linux下ip地址查询
  14. Bug 5323844-IMPDP无法导入远程数据库同义词的同义词
  15. 1080. Graduate Admission (30)-排序
  16. Try2Hack 过关技巧和密码
  17. BZOJ1699: [Usaco2007 Jan]Balanced Lineup排队 - 线段树
  18. Day 15 内置函数 , 匿名函数.
  19. MT【155】单调有界必有极限
  20. Android 如何保存资源 Id 数组在 res/values/arrays.xml 里

热门文章

  1. python基础7--集合
  2. CentOS7.2下安装mongoDB3.2.8
  3. Android通过php插入查询SQL数据库
  4. php输出日志的实现
  5. 区分IE8 、IE9 的专属css hack
  6. CSS浏览器兼容问题集-第四部分
  7. [acmm week12]二分+dp+单调队列
  8. 20155117王震宇 实验三 敏捷开发与XP实践 实验报告
  9. js设置html区域隐藏和显示
  10. Spring Boot微服务框架的搭建