[NOI2006最大获利]

kgxw0430 2019-03-23 原文

最大权闭合子图模板题，美滋滋。

闭合子图

定义一张有向图的闭合子图$G_0$，那么对于子图中的任意一个节点$v$都没有一条连出子图外节点的边。

最大权闭合子图
我们给有向图中的每个点$u$赋一个可正可负的权值$w_i$，那么一个有向图的最大权闭合子图就是满足$\sum_{w_i}$最大的$G_0$。

解决方法
建立超级源点向所有正权值的点连容量为点权的边。
建立超级汇点，所有负权值的点向汇点连容量为点权绝对值的边。
原图中的边保留，容量为inf。
$\sum_{w_i>0}-maxflow$即为答案。

正确性
考虑最优值一定是$S$到正权点尽可能多流，负权点尽可能少流。所以我们先全选正权点。
现在从$S$—>$T$就是损失。想一下，如果我们从$S$流出了一条容量为$x$点权的边，它跑完最大流之后，跑不满对应的负权点到$T$的流，代表什么？代表选了这个点，花费比收益大。不过在网络流图中，你跑最大流，最坏情况对应的其实就是不选这个点。因为你是减去最大流，最大流最多也就是$w_x$。多个点结合，也是一样的效果。
所以我们跑完最大流，就是最小损失，$sum-maxflow$就是答案。

模板题:[NOI2006]最大获利
直接把每个收益建成新节点，从$s$连边。这个收益点向两个中转站连$inf$的边。中转站向$t$连容量为代价的边。
跑最大权闭合子图即为答案。

Coding

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+100;
const int inf=1e9;
int n,m,tot=1,cnt,s,t,sum,flow,maxflow,d[N],p[N],ver[N<<1],Next[N<<1],lin[N],edge[N<<1];
void add(int x,int y,int z){
    ver[++tot]=y;Next[tot]=lin[x];lin[x]=tot;edge[tot]=z;
    ver[++tot]=x;Next[tot]=lin[y];lin[y]=tot;edge[tot]=0;
}
bool bfs(){
    queue<int>q;
    memset(d,0,sizeof(d));
    d[s]=1,q.push(s);
    while(q.size()){
        int x=q.front();q.pop();
        for(int i=lin[x];i;i=Next[i]){
            int y=ver[i];
            if(!d[y]&&edge[i]){
                d[y]=d[x]+1;
                q.push(y);
                if(y==t)return 1;
            }
        }
    }
    return 0;
}
int dinic(int x,int flow){
    if(x==t) return flow;
    int rest=flow;
    for(int i=lin[x];i&&rest;i=Next[i]){
        int y=ver[i];
        if(edge[i]&&d[y]==d[x]+1){
            int k=dinic(y,min(edge[i],rest));
            if(!k) d[y]=0;
            rest-=k;edge[i]-=k;edge[i^1]+=k;
            if(!rest) return flow-rest;
        }
    }
    return flow-rest;
}
int main(){
    scanf("%d%d",&n,&m);
    s=0,t=n+m+1;cnt=n;
    for(int i=1;i<=n;++i) scanf("%d",&p[i]),add(i,t,p[i]);
    for(int i=1;i<=m;++i){
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        ++cnt;sum+=z;
        add(s,cnt,z);add(cnt,x,inf);add(cnt,y,inf);
    }
    while(bfs()){
        while(flow=dinic(s,inf)) maxflow+=flow;
    }
    printf("%d\n",sum-maxflow);
    return 0;
}