题意：

要建\(n\)个站，建第i个站的花费\(p_i\)。

有\(m\)个收益机会，当第\(A_i\)和第\(B_i\)个站都被建立时可以得到收益\(C_i\).

问最大收益为多少。

\(n\le5000,m\le50000,0\le C_i,p_i\le100\)

题解：

考虑刚开始你能获得全部收益，然后要丢掉一些亏钱的。。

考虑网络流求最小割。

对于所有站i,建立\(S \rightarrow i\)的边权为\(p_i\)的边.

对于所有机会i,建立\(A_i\rightarrow i+n\),\(B_i \rightarrow i+n\)边权为INF，以及\(i+n \rightarrow T\),边权为\(C_i\).

那么就是最小割了

过程：

网络流日常打错：

1.bfs忘加必须有流量的限制。。

代码：

const int N=510,M=250010;int n,m;int p[N];struct PEO {    int a,b,v;    inline void in() {        read(a); read(b); read(v);    }}a[M];namespace FLOW {    const int ALL=N+M,EDGE=(N+M*3)<<1;    int S,T;    int head[ALL],nxt[EDGE],to[EDGE],cap[EDGE],lst=1;    inline void adde(int x,int y,int c) {        nxt[++lst]=head[x]; to[lst]=y; cap[lst]=c; head[x]=lst;    }    inline void con(int x,int y,int c) {        adde(x,y,c); adde(y,x,0);    }    int stp[ALL];    inline bool bfs(int S) {        queue
    
      que; mem(stp,63);        que.push(S); stp[S]=0;         while(!que.empty()) {            int u=que.front(); que.pop();            for(int i=head[u];i;i=nxt[i]) {                int v=to[i];                if(cap[i] && stp[v]>stp[u]+1) {                    stp[v]=stp[u]+1;                    que.push(v);                }            }        }        return stp[T]!=stp[0];    }    int cur[ALL];    inline int dfs(int u,int f) {        if(!f || u==T) return f;        for(int &i=cur[u];i;i=nxt[i]) {            int v=to[i];            if(stp[v]==stp[u]+1 && cap[i]) {                int flow=dfs(v,min(f,cap[i]));                if(flow) {                    cap[i]-=flow; cap[i^1]+=flow;                    return flow;                }            }        }        return 0;    }    inline int Dinic() {        int Flow=0,add=0;        while(bfs(S)) {            memcpy(cur,head,sizeof(head));            do {add=dfs(S,INF); Flow+=add;} while(add);        }        return Flow;    }    inline void Construct() {        S=n+m+1; T=S+1;        for(int i=1;i<=n;i++) {            con(S,i,p[i]);        }        for(int i=1;i<=m;i++) {            con(a[i].a,i+n,INF);            con(a[i].b,i+n,INF);            con(i+n,T,a[i].v);        }    }    inline int main() {        Construct();        // printf("%lld %lld %lld %lld\n",S,T,lst,EDGE);        return Dinic();    }}int sum=0;signed main() {    read(n); m=n*n;    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++) {            int p=(i-1)*n+j;            a[p].a=i; a[p].b=j; read(a[p].v);            sum+=a[p].v;        }    for(int i=1;i<=n;i++) read(p[i]);    int ans=FLOW::main();    printf("%d\n",sum-ans);    return 0;}
    

用时：25min