[$\Large\color{#FFBBFF}\textit{Tian-Xing's blog}$](https://Tian-Xing.github.io)
------------
# Description
[传送门](https://www.luogu.com.cn/problem/P4174)
------------
# Solution
经典的最大权闭合子图问题。
首先$S$向每个中转站连容量为费用的有向边。
每个群体向$T$连容量为收益的有向边。
如果一个中转站的点被割了，那么相当于建立这个中转站；如果一个群体被割了相当于不选这个群体。
那么答案就是所有群体的利益减去最小割。
由于每个群体有必须使用的中转站，所以把必须使用的中转站向群体连容量为$INF$的边，这样要不就是割掉群体（不选这个群体），要不就是割掉中转站（建立中转站），$INF$边的作用是避免冲突。
------------
# Code
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 999999999;
const int N = 500050;
const int M = 400050;
int head[N], num = 1, n, m, s, t, ans, maxflow, dis[N];
struct Node
{
int next, to, dis;
} edge[M * 2];
void Addedge(int u, int v, int w)
{
edge[++num]= (Node){head[u], v, w};
head[u] = num;
}
template <class T>
void Read(T &x)
{
x = 0; int p = 0; char st = getchar();
while (st < '0' || st > '9') p = (st == '-'), st = getchar();
while (st >= '0' && st <= '9') x = (x << 1) + (x << 3) + st - '0', st = getchar();
x = p ? -x : x;
return;
}
template <class T>
void Put(T x)
{
if (x < 0) putchar('-'), x = -x;
if (x > 9) Put(x / 10);
putchar(x % 10 + '0');
return;
}
bool Bfs()
{
queue<int> q;
for (int i = 0; i <= t; i++) dis[i] = 0;
dis[s] = 1; q.push(s);
while (!q.empty())
{
int u = q.front(); q.pop();
for (int i = head[u]; i; i = edge[i].next)
if (!dis[edge[i].to] && edge[i].dis)
{
dis[edge[i].to] = dis[u] + 1;
q.push(edge[i].to);
if (edge[i].to == t) return 1;
}
}
return 0;
}
int Dinic(int x, int flow)
{
if (x == t || !flow) return flow;
int rest = flow;
for (int i = head[x]; i && rest; i = edge[i].next)
if (edge[i].dis && dis[edge[i].to] == dis[x] + 1)
{
int v = edge[i].to;
int tmp = Dinic(v, min(rest, edge[i].dis));
rest -= tmp;
edge[i].dis -= tmp;
edge[i ^ 1].dis += tmp;
if (!tmp) dis[v] = 0;
}
return flow - rest;
}
void Add(int u, int v, int w)
{
Addedge(u, v, w);
Addedge(v, u, 0);
return;
}
int Maxflow()
{
int maxflow = 0, tmp;
while (Bfs())
{
tmp = Dinic(s, INF);
if (tmp) maxflow += tmp;
}
return maxflow;
}
int main()
{
Read(n); Read(m);
s = 0; t = n + m + 1;
for (int i = 1, p; i <= n; i++) Read(p), Add(s, i, p);
for (int i = 1, a, b, c; i <= m; i++)
{
Read(a); Read(b);Read(c);
ans += c;
Add(i + n, t, c);
Add(a, i + n, INF);
Add(b, i + n, INF);
}
Put(ans - Maxflow());
return 0;
}
```