P4174 [NOI2006]最大获利（网络流）

P4174 [NOI2006]最大获利

还是最大权闭合子图的题

对于每个中转站$k$：$link(k,T,P_k)$

对于每个用户$i$、中转站$A_i,B_i$、贡献$C_i$

$link(S,i,C_i)$

$link(i,A_i,inf)$

$link(i,B_i,inf)$

蓝后就可以跑最小割辣

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

#define N 100005

#define W 4000005

#define inf 2000000000

int n,m,d[N],cur[N],tot,S,T; bool vis[N];

queue <int> h;

int cnt=,hd[N],nxt[W],ed[N],poi[W],val[W];

inline void adde(int x,int y,int v){

    nxt[ed[x]]=++cnt, hd[x]=hd[x]?hd[x]:cnt,

    ed[x]=cnt, poi[cnt]=y, val[cnt]=v;

}

inline void link(int x,int y,int v){adde(x,y,v),adde(y,x,);}

bool bfs(){

    memset(vis,,sizeof(vis));

    h.push(S); vis[S]=;

    while(!h.empty()){

        int x=h.front(); h.pop();

        for(int i=hd[x];i;i=nxt[i]){

            int to=poi[i];

            if(!vis[to]&&val[i]>)

                vis[to]=,d[to]=d[x]+,h.push(to);

        }

    }return vis[T];

}

int dfs(int x,int a){

    if(x==T||a==) return a;

    int F=,f;

    for(int &i=cur[x];i;i=nxt[i]){

        int to=poi[i];

        if(d[to]==d[x]+&&(f=dfs(to,min(a,val[i])))>)

            a-=f,F+=f,val[i]-=f,val[i^]+=f;

        if(!a) break;

    }return F;

}

int dinic(){

    int re=;

    while(bfs()){

        for(int i=;i<=T;++i) cur[i]=hd[i];

        re+=dfs(S,inf);

    }return re;

}

int main(){

    scanf("%d%d",&n,&m); int q1,q2,w;

    S=n+m+; T=S+;

    for(int i=;i<=n;++i)

        scanf("%d",&w),link(i,T,w);

    for(int i=;i<=m;++i){

        scanf("%d%d%d",&q1,&q2,&w);

        tot+=w; link(S,i+n,w);

        link(i+n,q1,inf); link(i+n,q2,inf);

    }printf("%d",tot-dinic());

    return ;

}