题目传送门(BZOJ)
>原文链接<

题解 :

最大权闭合图 : 选了一个点,那么这个点可到达的所有点都要选, 求最大点权和。

建图套路 :

  1. 源点连正权点,边权为正权点权。
  2. 负权点连汇点,边权为点权相反数。
  3. 原图有的边连边,权值为INF。

答案就是正权点权和-最小割(即最大流)

对于本题来说,负权就是代价 P_i 正权就是获利 C_i 。按以上套路连点即可。

具体的,

i \to T \; val = p[i]

S \to i+n\; val = c[i]

i+n\to a[i]\; val = INF

i+n \to b[i]\; val = INF

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)using namespace std;char buf[100000],*p1,*p2;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}const int N = 210000;const int S = N-1, T = S-1;const int INF = 1<<30;struct Edge { int to, val; Edge *next, *back;}*h[N],e[N<<1];inline void Add_Edge(int u, int v, int w) { static int _; Edge *tmp = &e[++_]; tmp->to = v; tmp->val = w; tmp->next = h[u]; tmp->back = &e[_+1]; h[u] = tmp; tmp = &e[++_]; tmp->to = u; tmp->val = 0; tmp->next = h[v]; tmp->back = &e[_-1]; h[v] = tmp;}queue<int> q;int dep[N];bool bfs() { while(!q.empty()) q.pop(); memset(dep, 0, sizeof dep); dep[S] = 1; q.push(S); while(!q.empty()) { int u = q.front(); q.pop(); rev(i, u) if(!dep[i->to] && i->val) { dep[i->to] = dep[u] + 1; if(i->to == T) return 1; q.push(i->to); } } return 0;}int dfs(int p, int mf) { if(p == T) return mf; int nf = 0; rev(i, p) if(dep[i->to] == dep[p]+1 && i->val) { int tmp = dfs(i->to, min(mf-nf, i->val)); if(!tmp) dep[i->to] = 0; nf += tmp; i->val -= tmp; i->back->val += tmp; if(nf == mf) break; } return nf;}int dinic() { int ret = 0; while(bfs()) ret += dfs(S, INF); return ret;}int main() { int n = rd(), m = rd(), sum = 0; for(int i = 1; i <= n ; i ++ ) Add_Edge(i, T, rd()); for(int i = 1; i <= m ; i ++ ) { int u = rd(), v = rd(), w = rd(); sum += w; Add_Edge(S, i+n, w); Add_Edge(i+n, u, INF); Add_Edge(i+n, v, INF); } printf("%d\n", sum-dinic());}