本文共 4109 字，大约阅读时间需要 13 分钟。
学习链接
思路
将所有的活动与超级源点连起来，边权为活动的活跃值；学生与超级汇点连起来，边权为邀请学生的花费；将活动与所需要的学生连边，边权为\(inf\)。最后答案为所有活动的活跃值之和减去最小割。
代码实现如下
#include #include
q; int maxflow, tot, s, t; int head[maxn], d[maxn]; void init() { tot = maxflow = 0; memset(head, -1, sizeof(head)); } struct edge { int v, w, next; }ed[maxn*maxn]; void add(int u, int v, int w) { ed[tot].v = v; ed[tot].w = w; ed[tot].next = head[u]; head[u] = tot++; ed[tot].v = u; ed[tot].w = 0; ed[tot].next = head[v]; head[v] = tot++; } bool bfs() { memset(d, 0, sizeof(d)); d[s] = 1; while(!q.empty()) q.pop(); q.push(s); int x; while(!q.empty()) { x = q.front(); q.pop(); for(int i = head[x]; ~i; i = ed[i].next) { if(ed[i].w && !d[ed[i].v]) { d[ed[i].v] = d[x] + 1; q.push(ed[i].v); if(ed[i].v == t) return 1; } } } return 0; } int dinic(int x, int flow) { if(x == t) return flow; int res = flow, k, v; for(int i = head[x]; ~i && res; i = ed[i].next) { v = ed[i].v; if(ed[i].w && d[v] == d[x] + 1) { k = dinic(v, min(res, ed[i].w)); if(!k) d[v] = 0; ed[i].w -= k; ed[i^1].w += k; res -= k; } } return flow - res; } int work() { int flow = 0; while(bfs()) { while(flow = dinic(s, inf)) maxflow += flow; } return maxflow; }}f;int main() {#ifndef ONLINE_JUDGE FIN;#endif scanf("%d%d", &n, &m); f.s = 0, f.t = n + m + 1; f.init(); for(int i = 1; i <= m; ++i) { scanf("%d", &x); f.add(n + i, f.t, x); } int sum = 0; for(int i = 1; i <= n; ++i) { scanf("%d%d", &x, &num); f.add(f.s, i, x); sum += x; while(num--) { scanf("%d", &x); f.add(i, n + x, inf); } } printf("%d\n", sum - f.work()); return 0;}
思路
将智慧值的和与智力消耗值的和的差值为正的与源点连接，边权为差值，将智慧值的和与智力消耗值的和的差值为负的与汇点连接，边权为差值的绝对值，有前置技能的则将该技能与其前置技能点连边，边权为\(inf\)，最后跑最大权闭合子图即可。
代码实现如下
#include #include
q; int maxflow, tot, s, t; int head[maxn], d[maxn]; void init() { tot = maxflow = 0; memset(head, -1, sizeof(head)); } struct edge { int v, w, next; }ed[maxn*maxn]; void add(int u, int v, int w) { ed[tot].v = v; ed[tot].w = w; ed[tot].next = head[u]; head[u] = tot++; ed[tot].v = u; ed[tot].w = 0; ed[tot].next = head[v]; head[v] = tot++; } bool bfs() { memset(d, 0, sizeof(d)); d[s] = 1; while(!q.empty()) q.pop(); q.push(s); int x; while(!q.empty()) { x = q.front(); q.pop(); for(int i = head[x]; ~i; i = ed[i].next) { if(ed[i].w && !d[ed[i].v]) { d[ed[i].v] = d[x] + 1; q.push(ed[i].v); if(ed[i].v == t) return 1; } } } return 0; } int dinic(int x, int flow) { if(x == t) return flow; int res = flow, k, v; for(int i = head[x]; ~i && res; i = ed[i].next) { v = ed[i].v; if(ed[i].w && d[v] == d[x] + 1) { k = dinic(v, min(res, ed[i].w)); if(!k) d[v] = 0; ed[i].w -= k; ed[i^1].w += k; res -= k; } } return flow - res; } int work() { int flow = 0; while(bfs()) { while(flow = dinic(s, inf)) maxflow += flow; } return maxflow; }}f;int main() {#ifndef ONLINE_JUDGE FIN;#endif scanf("%d", &n); f.s = 0, f.t = n + 1; f.init(); int sum = 0; for(int i = 1; i <= n; ++i) { scanf("%d%d", &x, &y); if(x - y >= 0) f.add(f.s, i, x - y), sum += x - y; else f.add(i, f.t, y - x); } while(~scanf("%d%d", &u, &v)) { f.add(v, u, inf); } printf("%d\n", sum - f.work()); return 0;}