题意
现有n个基站待建。建立一个基站需要付出某个特定的代价。建好的基站之间可以相互通信。有m个工程项目，完成某个工程需要基站a与b可以相互通信，完成后获得报酬c。求最大可以获得的报酬。
解题
完成项目的先导条件是修建基站a，b。即所选子图的出边所指的点依然在子图中。符合闭合图定义。故此题就是求最大权闭合子图。
将工程项目作为X部，点权值为报酬c。
将基站作为Y部，点权值为修建代价（负权值）。
然后根据先导条件将X部与Y部连边。
设立一个源点S，一个汇点T。
从S到X部点连一条容量为c的有向弧；
从Y部点到T连一条容量为修建代价的绝对值的有向弧；
X部与Y部之间有向弧的容量为无穷大。
跑一边dinic算法求出最大流。
X部权值之和减去最大流即为所求。
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
#include <string>
#define INF 0x3f3f3f3f
using namespace std;long long S,T;//源点和汇点
const long long maxe=5e5+1000;
const long long maxv=5e5+7;
struct edge
{long long to,w,next;
}e[maxe<<1];
long long head[maxv<<1],depth[maxv],cnt;
void init()
{memset(head,-1,sizeof(head));cnt=-1;
}
void add_edge(long long u,long long v,long long w)
{e[++cnt].to=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;
}
void _add(long long u,long long v,long long w)
{add_edge(u,v,w);add_edge(v,u,0);
}bool bfs()
{queue<long long> q;while(!q.empty()) q.pop();memset(depth,0,sizeof(depth));depth[S]=1;q.push(S);while(!q.empty()){long long u=q.front();q.pop();for(long long i=head[u];i!=-1;i=e[i].next){if(!depth[e[i].to] && e[i].w>0){depth[e[i].to]=depth[u]+1;q.push(e[i].to);}}}if(!depth[T]) return false;return true;
}
long long dfs(long long u,long long flow)
{if(u==T) return flow;long long ret=0;for(long long i=head[u];i!=-1 && flow;i=e[i].next){if(depth[u]+1==depth[e[i].to] && e[i].w!=0){long long tmp=dfs(e[i].to,min(e[i].w,flow));if(tmp>0){flow-=tmp;ret+=tmp;e[i].w-=tmp;e[i^1].w+=tmp;}}}return ret;
}
long long Dinic()
{long long ans=0;while(bfs()){ans+=dfs(S,INF);}return ans;
}int main()
{long long n,m;while(~scanf("%lld%lld",&n,&m)){init();S=0,T=n+m+1;for(long long i=1;i<=n;i++){long long c;scanf("%lld",&c);_add(m+i,T,c);}long long sum=0;for(long long i=1;i<=m;i++){long long a,b,c;scanf("%lld%lld%lld",&a,&b,&c);_add(i,a+m,INF);_add(i,b+m,INF);_add(S,i,c);sum+=c;}printf("%lld\n",sum-Dinic());}return 0;
}