https://www.luogu.com.cn/problem/P4174
最小割
看很多人都是用最大权闭合子图来做的，其实就是对于每个用户、节点都建立点，然后用户是正权（获得收益），通讯节点是负权（需要成本），然后用户向所需要的节点连边，表示如果想得到这个正权，就必须把所需的负权节点也选上：也就是所选子图必须闭合
所以就用常规的做法，建模成网络流，(S) 向所有节点连流量为成本的边，用户向 (T) 连流量为收益的边，用户与节点的边流量为无穷大，就可以最小割了
但这种连边方式还有一种理解，就是割点 (S) 和节点的边代表建立这个节点，损失这些成本，割掉用户和 (T) 的边代表放弃这个用户，损失这些收益
然后对于一个用户和它需要的节点，不能既不建立节点、也不放弃这个用户（就是和 (S,T) 的边分别都保留），所以要在它们之间连流量无穷的边，割不掉，表示矛盾
这是基于用流量无穷表示矛盾的一种做法
还有一种连边方式不同的，是基于表示两点之间的关系
先考虑某两个节点 (x,y)，有一个用户 (i) 需要它们两个
显然，一个点不能同时和 (S,T) 相连，需要割掉一些边（也不可能都不相连，这样不是最小割），我们设与 (S) 相连表示这个节点要建立，与 (T) 相连则不建立。然后有四种可能
- (x,y) 都选，损失它们的成本和，也就是 (p_x+p_y)，要割掉 (c,d)，那么 (c+d=p_x+p_y)
- (x,y) 都不选，损失用户的收益，(a+b=C_i)
- (x) 选 (y) 不选，(b+e+c=C_i+p_x)
- (x) 不选 (y) 选，(a+e+d=C_i+p_y)
那么解上面的方程，得到 (a=b=e=dfrac{C_i}{2},c=p_x,d=p_y)
那么将其推广到有 (n) 个节点的情况，就是每个节点向 (T) 连流量是 (p_i) 的边；从 (S) 向每个节点连所有需要它的用户的 (C) 值之和的一般的边；用户所需的两个点互相连流量 (dfrac{C_i}{2}) 的 双向边
为了避免出现浮点数，可以把所有权值都乘二
这种方法还是从16年集训队论文里看的，但不是这个题
不过这样做也有一定的局限性，就是用户只能同时需要两个节点，多了就不行了
代码是第二种方法的
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN puts("")
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=getchar();}
return y?x:-x;
}
#define N 5006
#define M 300006
struct Graph{
int fir[N],fir_[N],nex[M],to[M],tot;
long long w[M];
inline void add(int u,int v,long long W,int flag=1){
to[++tot]=v;w[tot]=W;
nex[tot]=fir[u];fir[u]=tot;
if(flag) add(v,u,0,0);
}
}G;
int n,m,S,T;
int deep[N];
int left,right,que[N];
inline int bfs(){
std::memset(deep,0,sizeof deep);
left=right=0;
que[0]=S;deep[S]=1;
reg int u;
while(left<=right){
u=que[left++];
for(reg int v,i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(deep[v]||!G.w[i]) continue;
deep[v]=deep[u]+1;que[++right]=v;
if(v==T) return 1;
}
}
return 0;
}
long long dfs(reg int u,long long now=1e18){
if(u==T) return now;
long long res=now;
for(reg int v,&i=G.fir_[u];i;i=G.nex[i]){
v=G.to[i];
if(deep[v]!=deep[u]+1||!G.w[i]) continue;
long long k=dfs(v,std::min(res,G.w[i]));
if(!k) deep[v]=0;
else G.w[i]-=k,G.w[i^1]+=k,res-=k;
if(!res) break;
}
return now-res;
}
inline long long dinic(){
long long ans=0,now;
while(bfs()){
std::memcpy(G.fir_,G.fir,sizeof G.fir);
while(now=dfs(S)) ans+=now;
}
return ans;
}
long long sum[M];
int main(){
n=read();m=read();
S=n+1;T=n+2;
G.tot=1;
for(reg int i=1;i<=n;i++) G.add(i,T,read()*2);
long long all=0;
for(reg int a,b,c,i=1;i<=m;i++){
a=read();b=read();c=read();
G.add(a,b,c);G.add(b,a,c);
sum[a]+=c;sum[b]+=c;all+=c*2;
}
for(reg int i=1;i<=n;i++) G.add(S,i,sum[i]);
n+=2;
printf("%lld
",(all-dinic())>>1);
return 0;
}