题目概述

有 $n$ 个点 $m$ 条边，每个点需要花费 $p_i$ 购买，每条边可以得到 $c_i$ 的价值。现在要购买一些点，如果一条边两端的点都被购买了，就可以得到这条边的价值。求最大价值。

解题报告

如果一条边要得到价值，那么这条边的两端必须选，这就是闭合图的要求。所以我们把每条边也当成点，然后建图，刷最大权闭合图就行了。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=55000,maxm=155000,MAXINT=((1<<30)-1)*2+1;

int n,m,ans,E,lnk[maxn+5],son[(maxm<<1)+5],nxt[(maxm<<1)+5];
int cur[maxn+5],que[maxn+5],ti,vis[maxn+5],dis[maxn+5];
pair<int,int> e[(maxm<<1)+5];

inline void Add(int x,int y,int z){
    son[E]=y;nxt[E]=lnk[x];e[E]=mp(0,z);lnk[x]=E++;
    son[E]=x;nxt[E]=lnk[y];e[E]=mp(0,0);lnk[y]=E++;
}
inline bool Bfs(int s,int t){
    int Head=0,Tail=0;ti++;que[++Tail]=s;vis[s]=ti;dis[s]=0;
    while (Head!=Tail)
        for (int x=que[++Head],j=lnk[x],u;~j;j=nxt[j])
            if (vis[u=son[j]]<ti&&e[j].fr<e[j].sc) que[++Tail]=u,vis[u]=ti,dis[u]=dis[x]+1;
    return vis[t]==ti;
}
int Dfs(int x,int gl,int MIN=MAXINT){
    if (x==gl||!MIN) return MIN;int f=0,now;
    for (int &j=cur[x];~j;j=nxt[j])
        if (dis[x]+1==dis[son[j]]&&(now=Dfs(son[j],gl,min(MIN,e[j].sc-e[j].fr)))){
            f+=now;e[j].fr+=now;e[j^1].fr-=now;
            if (!(MIN-=now)) break;
        }
    return f;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);E=0;memset(lnk,255,sizeof(lnk));
    for (int i=1,x;i<=n;i++) scanf("%d",&x),Add(i,n+m+1,x);
    for (int i=1,x,y,z;i<=m;i++,ans+=z)
        scanf("%d%d%d",&x,&y,&z),Add(0,n+i,z),Add(n+i,x,MAXINT),Add(n+i,y,MAXINT);
    while (Bfs(0,n+m+1)) memcpy(cur,lnk,sizeof(lnk)),ans-=Dfs(0,n+m+1);
    return printf("%d\n",ans),0;
}