首先get知识点讲解（活动和邀请学生的题，主要看如何建图的和结论！很重要！）：
https://blog.csdn.net/Cold_Chair/article/details/52841351
结论：最大权闭合子图 = 正点和-最小割。（同时，如果题目要求不仅要是最大权，并且要求"活动"点数还最少，那代码不用变，照样满足。）
这种题型都是直接套这个结论即可。
大致思路：
就是用结论“正点和-最小割=最大权闭合子图”
建图如下：
代码：
[cpp] view plain copy #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define maxn 5010 #define maxm 50100 #define inf 0x3f3f3f3f using namespace std; struct Edge{ int v,c,next; Edge(int v,int c,int next):v(v),c(c),next(next){} Edge(){} }e[maxm*6+maxn*2]; int p[maxn+maxm]; int cnt,n,m,T; void init(){ cnt=0; memset(p,-1,sizeof(p)); } void insert(int u,int v,int c){ e[cnt]=Edge(v,c,p[u]); p[u]=cnt++; } int d[maxn+maxm]; bool bfs(){ memset(d,-1,sizeof(d)); queue<int>q; d[0]=0; q.push(0); while(!q.empty()){ int u=q.front();q.pop(); for(int i=p[u];i!=-1;i=e[i].next){ int v=e[i].v; if(e[i].c>0&&d[v]==-1){ //printf("%d->%d(%d)\n",u,v,d[u]+1); d[v]=d[u]+1; q.push(v); } } } return d[T]!=-1; } int dfs(int u,int flow){ if(u==T)return flow; int res=0; for(int i=p[u];i!=-1;i=e[i].next){ int v=e[i].v; if(e[i].c>0&&d[v]==d[u]+1){ int tmp=dfs(v,min(flow,e[i].c)); e[i].c-=tmp; flow-=tmp; e[i^1].c+=tmp; res+=tmp; if(flow==0) break; } } if(res==0) d[u]=-1; return res; } int dinic(){ int res=0; while(bfs()){ // printf("here!\n"); res+=dfs(0,inf); } return res; } int main(){ init(); int p,a,b,c,sum=0; scanf("%d%d",&n,&m); T=n+m+1;//汇点 for(int i=1;i<=n;i++){ scanf("%d",&p); insert(i+m,T,p); //课程放右边 insert(T,i+m,0); } for(int i=1;i<=m;i++){ scanf("%d%d%d",&a,&b,&c); sum+=c; insert(i,a+m,inf); insert(a+m,i,0); insert(i,b+m,inf); insert(b+m,i,0); insert(0,i,c); //用户放左边 insert(i,0,0); } printf("%d\n",sum-dinic()); return 0; }