P4174 [NOI2006] 最大获利

· · 题解

一种不同的做法。

因为一个人只会连两个不同的点，所以可以把人看成边，现在我们要求的就是一个点集 V^\prime 和这些点集里面的边 E^\prime 的贡献最大，即

\max\{-\sum_{v\in V^\prime}P_v+\sum_{e\in E^\prime}w_e\}

也就是

\dfrac{1}{2}\max\{-\sum_{v\in V^\prime}(2P_v-sumw_v)-C[V^\prime,\overline{V^\prime}]\}

其中 C[V^\prime,\overline{V^\prime}] 表示 V^\prime 和 V^\prime 的补集之间的所有边的边权和。

到这里就已经变成了一个把点划分成集合的问题了，不难想到用网络流来解决，按照如下方法建图，为了保证边权非负，我们给每一条点和源/汇相连的边加上一个权值 U。

答案即为 \dfrac{\sum_{i=1}^n (sumw_i-2P_i)+Un-maxflow}{2}

复杂度为 \mathcal O(\operatorname{maxflow}(n,n+m))

int n,m;
int head[N],cnt;
int dep[N],S,T,U;
int a[N],sw[N];
ll ans,maxflow;

struct Edge{
    int to,next,flow;
}e[M<<1];

void add(int x,int y,int c){
    e[++cnt]=(Edge){y,head[x],c},head[x]=cnt;
    e[++cnt]=(Edge){x,head[y],0},head[y]=cnt;
}

bool bfs(){
    memset(dep,0,sizeof(dep));
    queue<int> q;
    q.push(S),dep[S]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        RepG(i,u){
            int v=e[i].to;
            if(e[i].flow&&!dep[v]){
                dep[v]=dep[u]+1;
                q.push(v);
                if(v==T)return true;
            }
        }
    }
    return false;
}

int dfs(int u,int flow){
    if(u==T)return flow;
    int tmp=0,k;
    for(int i=head[u];~i&&tmp<flow;i=e[i].next){
        int v=e[i].to;
        if(e[i].flow&&dep[v]==dep[u]+1){
            k=dfs(v,min(e[i].flow,flow-tmp));
            if(!k)dep[v]=0;
            e[i].flow-=k,e[i^1].flow+=k;
            tmp+=k;
        }
    }
    return tmp;
}

void dinic(){
    while(bfs())
        maxflow+=dfs(S,inf);
}

int main()
{
    # ifdef hibike
    freopen("testdata.in","r",stdin);
    freopen("test1.out","w",stdout);
    # endif
    memset(head,-1,sizeof(head)),cnt=1;
    read(n),read(m);
    S=n+1,T=S+1;
    Rep(i,1,n)read(a[i]);
    Rep(i,1,m){
        int x,y,c;
        read(x),read(y),read(c);
        add(x,y,c),add(y,x,c);
        sw[x]+=c,sw[y]+=c;
    }
    Rep(i,1,n)U=max(U,2*a[i]-sw[i]);
    U++;
    Rep(i,1,n)add(S,i,sw[i]-2*a[i]+U),ans+=sw[i]-2*a[i]+U;
    Rep(i,1,n)add(i,T,U);
    dinic();
    printf("%lld\n",(ans-maxflow)/2);
    return 0;
}