题目大意

给出m个通讯站建造成本$A_i$

给出n个用户，只要建造了他需要的两个通讯站就能得到收益$C_i$

求出最大获利(获利=总收益-总成本)

数据范围

$n\leqslant 5000,m \leqslant 50000,0\leqslant A_i,C_i\leqslant 100$

题解

要想获得每一个用户的收益，一定要建造他需要的两个通讯站(已经建造的就无需再次建造)

条件式的收益，可以马上想到最大权闭合图

所以就从源点向每一个用户连一条容量为其用户收益的边，从每一个用户向这个用户需要的两个通讯站各连一条容量为无限大的边，再从每一位通讯站向汇点连一条容量为其建造成本的边

设最小割为$ans$，则$result=\sum_{i=1}^{n}C_i-ans$

关于最大权闭合子图可以看这个

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define inf 0x7fffffff
using namespace std;

struct edge{int to,next,c;}e[505000];
int d[205000],last[205000];
int n,m,ans,sum,s,t,et;
inline void addedge(int u,int v,int c){
    e[++et].to=v;e[et].c=c;e[et].next=last[u];last[u]=et;
    e[++et].to=u;e[et].c=0;e[et].next=last[v];last[v]=et;
}

inline int bfs(){
    memset(d,-1,sizeof(d));
    queue <int> q;q.push(s);d[s]=0;
    while(!q.empty()){
        int h=q.front();q.pop();
        goedge(i,h)
            if ((d[e[i].to]==-1)&&(e[i].c>0)){
                d[e[i].to]=d[h]+1;
                q.push(e[i].to);
            }
    }
    if (d[t]<0) return 0;
    return 1;
}

int dinic(int x,int flow){
    if (x==t) return flow;int a,used=0;
    goedge(i,x)
        if ((e[i].c>0)&&(d[e[i].to]==d[x]+1)){
            a=dinic(e[i].to,min(flow-used,e[i].c));
            e[i].c-=a;e[i^1].c+=a;used+=a;
            if (flow==used) return used;
        }
    if (!used) d[x]=-1;
    return used;
}

int main(){
    scanf("%d%d",&n,&m);
    s=0;t=n+m+1;et=1;
    For(i,1,n){int a;scanf("%d",&a);addedge(i,t,a);}
    For(i,1,m){
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        addedge(i+n,a,inf);addedge(i+n,b,inf);addedge(0,i+n,c);
        sum+=c;
    }
    while (bfs()) ans+=dinic(s,inf);
    printf("%d\n",sum-ans);
    return 0;
}