这道题属于网络流的模板题，不是很了解网络流的可以看看这篇介绍
首先有一个定理
最大流最小割定理：最大流最小割定理是理论的重要定理。是指在一个网络流中，能够从源点到达汇点的最大流量等于如果从网络中移除就能够导致网络流中断的边的集合的最小容量和。即在任何网络中，最大流的值等于最小割的容量
题目中又提到了另一个定理，即最大权闭合子图的权值等于所有正权点之和减去最小割。
正如题目中所说对于一般的图来说：首先建立源点s和汇点t，将源点s与所有权值为正的点相连，容量为权值；将所有权值为负的点与汇点t相连，容量为权值的绝对值；权值为0的点不做处理；同时将原来的边容量设置为无穷大。
首先，建立模型，我们把每个活动看做一个点，权值为正(获得的班级活跃值)，将每个学生也看做一个点，权值为负(学生消耗的班级活跃值)，将权值为正的点与源点相连，并将对应边容量设为权值，将权值为负的
点与汇点相连，容量设为权值的绝对值。建立模型还是很好理解的，活跃值只能从源点出发获得，与汇点相连的都是消耗的。
所以这个题实际上就是一个求最大流（最小割）的模板题；
我们先看一道例题来引进最大流模板
输入输出格式
输入格式：
第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）
输出格式：
一行，包含一个正整数，即为该网络的最大流。
1 #include2 using namespace std; 3 4 typedef struct Edge { 5 int u, v, w, next; 6 }Edge; 7 8 const int inf = 0x7f7f7f7f; 9 const int maxn = 10005;10 11 int cnt, dhead[maxn];12 int cur[maxn], dd[maxn];13 Edge dedge[maxn*maxn];14 int S, T, N;15 int n, m;16 17 18 void init() {19 memset(dhead, -1, sizeof(dhead));20 for(int i = 0; i < maxn; i++) dedge[i].next = -1;21 cnt = 0;22 }23 24 void adde(int u, int v, int w, int c1) {25 dedge[cnt].u = u; dedge[cnt].v = v; dedge[cnt].w = w; 26 dedge[cnt].next = dhead[u]; dhead[u] = cnt++;27 dedge[cnt].u = v; dedge[cnt].v = u; dedge[cnt].w = c1; 28 dedge[cnt].next = dhead[v]; dhead[v] = cnt++;29 }30 31 bool bfs(int s, int t, int n) {32 queue q;33 for(int i = 0; i < n; i++) dd[i] = inf;34 dd[s] = 0;35 q.push(s);36 while(!q.empty()) {37 int u = q.front(); q.pop();38 for(int i = dhead[u]; ~i; i = dedge[i].next) {39 if(dd[dedge[i].v] > dd[u] + 1 && dedge[i].w > 0) {40 dd[dedge[i].v] = dd[u] + 1;41 if(dedge[i].v == t) return 1;42 q.push(dedge[i].v);43 }44 }45 }46 return 0;47 }48 49 int dinic(int s, int t, int n) {50 int st[maxn], top;51 int u;52 int flow = 0;53 while(bfs(s, t, n)) {54 for(int i = 0; i < n; i++) cur[i] = dhead[i];55 u = s; top = 0;56 while(cur[s] != -1) {57 if(u == t) {58 int tp = inf;59 for(int i = top - 1; i >= 0; i--) {60 tp = min(tp, dedge[st[i]].w);61 }62 flow += tp;63 for(int i = top - 1; i >= 0; i--) {64 dedge[st[i]].w -= tp;65 dedge[st[i] ^ 1].w += tp;//异或1求的就是反向边，因为边是两条两条建立的66 //如0^1 = 1,1^0 = 1,2^1 = 3,3^1 = 2,4^1=5,5^1=4 以此类推67 //这样正向边^1就是反向边，反向边^1就是正向边 68 if(dedge[st[i]].w == 0) top = i;69 }70 u = dedge[st[top]].u;71 }72 else if(cur[u] != -1 && dedge[cur[u]].w > 0 && dd[u] + 1 == dd[dedge[cur[u]].v]) {73 st[top++] = cur[u];74 u = dedge[cur[u]].v;75 }76 else {77 while(u != s && cur[u] == -1) {78 u = dedge[st[--top]].u;79 }80 cur[u] = dedge[cur[u]].next;81 }82 }83 }84 return flow;85 }86 87 int main() {88 scanf("%d%d%d%d",&n,&m,&S,&T);89 init();int x,y,z;90 for(int i=0;i
有了模板之后，我们直接将主函数改一改，参数传进去就好了
1 #include2 using namespace std; 3 4 typedef struct Edge { 5 int u, v, w, next; 6 }Edge; 7 8 const int inf = 0x7f7f7f7f; 9 const int maxn = 500; 10 11 int cnt, dhead[maxn]; 12 int cur[maxn], dd[maxn]; 13 Edge dedge[maxn*maxn]; 14 int S, T, N; 15 int n, m; 16 17 18 void init() { 19 memset(dhead, -1, sizeof(dhead)); 20 for(int i = 0; i < maxn; i++) dedge[i].next = -1; 21 cnt = 0; 22 } 23 24 void adde(int u, int v, int w, int c1) { 25 dedge[cnt].u = u; dedge[cnt].v = v; dedge[cnt].w = w; 26 dedge[cnt].next = dhead[u]; dhead[u] = cnt++; 27 dedge[cnt].u = v; dedge[cnt].v = u; dedge[cnt].w = c1; 28 dedge[cnt].next = dhead[v]; dhead[v] = cnt++; 29 } 30 31 bool bfs(int s, int t, int n) { 32 queue q; 33 for(int i = 0; i < n; i++) dd[i] = inf; 34 dd[s] = 0; 35 q.push(s); 36 while(!q.empty()) { 37 int u = q.front(); q.pop(); 38 for(int i = dhead[u]; ~i; i = dedge[i].next) { 39 if(dd[dedge[i].v] > dd[u] + 1 && dedge[i].w > 0) { 40 dd[dedge[i].v] = dd[u] + 1; 41 if(dedge[i].v == t) return 1; 42 q.push(dedge[i].v); 43 } 44 } 45 } 46 return 0; 47 } 48 49 int dinic(int s, int t, int n) { 50 int st[maxn], top; 51 int u; 52 int flow = 0; 53 while(bfs(s, t, n)) { 54 for(int i = 0; i < n; i++) cur[i] = dhead[i]; 55 u = s; top = 0; 56 while(cur[s] != -1) { 57 if(u == t) { 58 int tp = inf; 59 for(int i = top - 1; i >= 0; i--) { 60 tp = min(tp, dedge[st[i]].w); 61 } 62 flow += tp; 63 for(int i = top - 1; i >= 0; i--) { 64 dedge[st[i]].w -= tp; 65 dedge[st[i] ^ 1].w += tp; 66 if(dedge[st[i]].w == 0) top = i; 67 } 68 u = dedge[st[top]].u; 69 } 70 else if(cur[u] != -1 && dedge[cur[u]].w > 0 && dd[u] + 1 == dd[dedge[cur[u]].v]) { 71 st[top++] = cur[u]; 72 u = dedge[cur[u]].v; 73 } 74 else { 75 while(u != s && cur[u] == -1) { 76 u = dedge[st[--top]].u; 77 } 78 cur[u] = dedge[cur[u]].next; 79 } 80 } 81 } 82 return flow; 83 } 84 85 int main() { 86 int k, u, v, w; 87 while(~scanf("%d %d", &n, &m)) { 88 init(); S = 0; T = n + m + 1; N = T + 1;//注意这里的边数不是单纯的n,而应该是n+m+2即N,n,m都是边数，加2是因为源点汇点 89 int pos = 0;//pos将正权值全加起来 90 for(int i = 1; i <= m; i++) { 91 scanf("%d", &w); 92 if(w != 0) adde(n+i, T, w, 0); 93 else adde(n+i, T, inf, 0);//权值为负的与汇点相连 94 } 95 for(int i = 1; i <= n; i++) { 96 scanf("%d %d", &w, &k); 97 pos += w; 98 if(w != 0) adde(S, i, w, 0); 99 else adde(S, i, inf, 0);100 for(int j = 0; j < k; j++) {101 scanf("%d", &v);102 adde(i, n+v, inf, 0);103 }104 }105 printf("%d\n", pos - dinic(S,T,N));//最大权闭合子图的权值等于所有正权点之和减去最小割。106 }107 }