tags：点和边之间存在依赖关系，可以考虑最大权闭合图。
首先建图，原先的点与汇点相连，边权为原来点的权值(负的)；原先的边与源点及这条边左右端点相连，边权分别为原来边的权值、无穷大、无穷大。然后，求出最小割，最后的答案就是 原来所有的边权和 - 最小割。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 500005; int n, m; struct Edge{int to, next, w;}e[N]; int head[N], tot; void Addedge(int u, int v, int w) { e[tot].to=v, e[tot].next=head[u], e[tot].w=w, head[u]=tot++; e[tot].to=u, e[tot].next=head[v], e[tot].w=0, head[v]=tot++; } //Dinic int dis[N], cur[N], q[N<<1], st, ed; bool bfs() { memset(dis, -1, sizeof(dis)); dis[st]=0; int tail=1, head2=1; q[++tail]=st; int u, v; while(head2<tail) { u=q[++head2]; for(int i=head[u]; i!=-1; i=e[i].next) { v=e[i].to; if(dis[v]!=-1 || e[i].w==0) continue; dis[v]=dis[u]+1; q[++tail]=v; if(v==ed) return true; } } return false; } int dfs(int x, int mx) { if(x==ed || mx==0) return mx; int f, flow=0, v, ret=0; for(int &i=cur[x]; i!=-1; i=e[i].next) { // &i v=e[i].to; if(dis[x]+1!=dis[v]) continue; if(f=dfs(v, min(mx, e[i].w))) { //不是== e[i].w-=f; e[i^1].w+=f; flow+=f; ret+=f; mx-=f; if(mx==0) break; } } if(ret==0) dis[x]=-1; return flow; } int Dinic() { int temp=0, maxflow=0; while(bfs()) { for(int i=1; i<=ed; i++) cur[i]=head[i]; //这个模板在这里cur[i]=head[i]，故加边时tot要放在后面，且head[]要定-1，否则很容易错 while(temp=dfs(st, INF)) maxflow+=temp; } return maxflow; } void solve() { int sum=0, pi; rep(i,1,n) { scanf("%d", &pi); Addedge(i, ed, pi); } int u, v, w; rep(i,1,m) { scanf("%d %d %d", &u, &v, &w); sum+=w; Addedge(i+n, u, INF); Addedge(i+n, v, INF); Addedge(st, i+n, w); } printf("%d ", sum-Dinic()); } void Init() { mes(head, -1); st=n+m+1, ed=st+1; } int main() { scanf("%d %d", &n, &m); Init(); solve(); return 0; }