最大权闭合子图要解决的就是在一张图中的有附属的选点问题：
有一张有向图，点权有正有负，如果点u被选中，那么从点u出发所有能到达的点【u的附属点】都要被选，求最大选点方案。
网络流：
建立源汇点S，T，
1、对于所有权值w非负的点，从S向该点连一条容量为w的边
2、对于所有权值w为负的点，从该点向T连一条容量为-w的边
3、对于原图的所有边，容量改为INF
最终答案 = 原图正权值和 - 最大流
原理：
实质为最小割，对于每一块附属关系，中间INF的边不能割去，要么割去连S的边，要么割去连T的边
1、若割去连S的边，即表示不选这一块点，要付出这块点正权值的代价
2、若割去连T的边，即表示选这一块点，要付出这块点的负权值的代价
所以最终用总正权值减去最小割就是最终的答案
例题
1497: [NOI2006]最大获利
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 5710 Solved: 2767
[Submit][Status][Discuss]
Description
新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。在前期市场调查和站址勘测之后，公司得到了一共N个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第i个通讯中转站需要的成本为Pi（1≤i≤N）。另外公司调查得出了所有期望中的用户群，一共M个。关于第i个用户群的信息概括为Ai, Bi和Ci：这些用户会使用中转站Ai和中转站Bi进行通讯，公司可以获益Ci。（1≤i≤M, 1≤Ai, Bi≤N） THU集团的CS&T公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 - 投入成本之和）
Input
输入文件中第一行有两个正整数N和M 。第二行中有N个整数描述每一个通讯中转站的建立成本，依次为P1, P2, …, PN 。以下M行，第(i + 2)行的三个数Ai, Bi和Ci描述第i个用户群的信息。所有变量的含义可以参见题目描述。
Output
你的程序只要向输出文件输出一个整数，表示公司可以得到的最大净获利。
Sample Input
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3
Sample Output
将用户和中继站看做点，用户的权值为收益，中继站的权值为建站费用【负数】，跑一遍最大权闭合子图就好了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define LL long long int
using namespace std;
const int maxn = 100005,maxm = 500005,INF = 2000000000;
inline int read(){
int out = 0,flag = 1;char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1;c = getchar();}
while (c >= 48 &&c <= 57) {out = out * 10 + c - 48;c = getchar();}
return out * flag;
}
int head[maxn],nedge = 0;
struct EDGE{
int to,f,next;
}edge[maxm];
inline void build(int u,int v,int w){
edge[nedge] = (EDGE){v,w,head[u]};
head[u] = nedge++;
edge[nedge] = (EDGE){u,0,head[v]};
head[v] = nedge++;
}
int N,M,tot = 0;
int d[maxn],S,T,cur[maxn];
bool vis[maxn];
bool bfs(){
fill(vis,vis + maxn,false);
queue<int> q;
d[S] = 0;
vis[S] = true;
q.push(S);
int u,to;
while (!q.empty()){
u = q.front();
q.pop();
for (int k = head[u]; k != -1; k = edge[k].next)
if (edge[k].f && !vis[to = edge[k].to]){
d[to] = d[u] + 1;
q.push(to);
vis[to] = true;
}
}
return vis[T];
}
int dfs(int u,int minf){
if (u == T || !minf) return minf;
int f,flow = 0,to;
if (cur[u] == -2) cur[u] = head[u];
for (int& k = cur[u]; k != -1; k = edge[k].next)
if (d[to = edge[k].to] == d[u] + 1 && (f = dfs(to,min(minf,edge[k].f)))){
edge[k].f -= f;
edge[k^1].f += f;
flow += f;
minf -= f;
if (!minf) break;
}
return flow;
}
int maxflow(){
int flow = 0;
while (bfs()){
fill(cur,cur + maxn,-2);
flow += dfs(S,INF);
}
return flow;
}
void init(){
fill(head,head + maxn,-1);
int a,b,c;
N = read();
M = read();
S = 0;
T = N + M + 1;
for (int i = 1; i <= N; i++) build(i,T,read());
for (int i = 1; i <= M; i++){
a = read();
b = read();
tot += (c = read());
build(S,N + i,c);
build(N + i,a,INF);
build(N + i,b,INF);
}
}
int main(){
init();
cout<<tot - maxflow()<<endl;
return 0;
}