据说是模板题…
求最大权闭合子图
最大权闭合子图参考这里
然后把题目的边看成原模板中的正权点,原先的点就看成原模板中的负权点,跑最大流求出最小割,然后用总的边权减去最小割即可

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
const int M=2e6+50;
const ll INF=1e18;
int n,m;
ll val[N];
struct Edge{
   
    int v;
    ll cap,flow;
    int next;
}edge[M];
int cnt,head[N];
void init(){
   
    cnt=0;
    memset(head,-1,sizeof(head));
}
void addEdge(int u,int v,ll cap,ll cost){
   
    edge[cnt]=Edge{
   v,cap,0,head[u]};
    head[u]=cnt++;
    edge[cnt]=Edge{
   u,0,0,head[v]};
    head[v]=cnt++;
}
int s,t;
int dep[N];
bool bfs(){
   
    queue<int> q;
    memset(dep,0,sizeof(dep));
    dep[s]=1;
    q.push(s);
    while(!q.empty()){
   
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=edge[i].next){
   
            int v=edge[i].v;
            ll w=edge[i].cap-edge[i].flow;
            if(w>0 && dep[v]==0){
   
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[t]!=0;
}
int cur[N];
ll dfs(int u,ll flow){
   
    if(u==t){
   
        return flow;
    }
    for(int &i=cur[u];i!=-1;i=edge[i].next){
   
        int v=edge[i].v;
        ll w=edge[i].cap-edge[i].flow;
        if(dep[v]==dep[u]+1 && w!=0){
   
            ll dis=dfs(v,min(w,flow));
            if(dis>0){
   
                edge[i].flow+=dis;
                edge[i^1].flow-=dis;
                return dis;
            }
        }
    }
    return 0;
}
ll dinic(){
   
    ll ans=0;
    while(bfs()){
   
        for(int i=0;i<=n+m;i++){
   
            cur[i]=head[i];
        }
        while(ll d=dfs(s,INF)){
   
            ans+=d;
        }
    }
    return ans;
}
int main(void){
   
    scanf("%d%d",&n,&m);
    s=0;
    t=n+m+1;
    init();
    ll w;
    int u,v;
    ll sum=0;
    for(int i=1;i<=n;i++){
   
        scanf("%lld",&w);
        addEdge(m+i,t,w,0);
    }
    for(int i=1;i<=m;i++){
   
        scanf("%d%d%lld",&u,&v,&w);
        sum+=w;
        addEdge(s,i,w,0);
        addEdge(i,m+u,INF,0);
        addEdge(i,m+v,INF,0);
    }
    ll ans=dinic();
    printf("%lld\n",sum-ans);
    return 0;
}