一种特殊的最大权闭合图的优化建图

详见胡波涛的论文吧《最小割模型在信息学竞赛中的应用》,我只是搬运一下。

关于为什么要学这个优化建图,我其实最开始认为实际运行上是差不了多少的,所以就没怎么关注。

今天写了一下,发现效率差距还是挺大的。

BZOJ
所以来简单说一下

刚好这道题模型比较简单,就以这道题来讲一下优化建图的方法。

不优化的话怎么建图?很简单,我们把这个看作一个最大权闭合图的模型,即用户为正点权,基站为负点权。
然后用户指向基站,按照普通的最大权闭合图来稿就行了。

这个算法的复杂度是$O(Maxflow(n+m,n+m))$

现在我们考虑优化建图的方法,因为一个用户唯一的对应两个基站,我们不妨把用户看作点,基站看作边。
即建一个新图$(V,E)$,我们发现我们选择的方案,对应的一定是一个点集$V_0$,因为边权都是正的,所以任意$(u,v)|u,v\in V_0$一定会被选择。

现在观察我们目标,即$Maximum\ \sum w_e-\sum w_u$,我们换一下目标,也就是$Minimum\ \sum w_u-\sum w_e$,接着我们令$d_u=\sum_{(u,v)\in e} w_e$,令$V_0$向$V_0$的补集$V_1$的割为$C$。
那么很显然上面的目标可以转化为
$Minimum \ \sum w_u-\frac{\sum d_u-C}{2}$

为了表达更方便我们系数倍增一下,就是
$Minimum \ \sum (2w_u-d_u)+C$

我们惊喜的发现这对赢了最小割的模型!
可以发现这个算法的复杂度是$O(Maxflow(n,n+m))$的,因为网络流的复杂度比较玄学,所以运行状况要优很多。

然后就做完了,注意需要加一个偏移值。

下面给出我的代码实现。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define up(i,j,n)        for(int i=j;i<=n;i++)
#define down(i,j,n)    for(int i=j;i>=n;i--)
#define cmax(a,b)        a=max(a,b)
#define cmin(a,b)        a=min(a,b)
#define Auto(i,node)    for(int i=LINK[node];i;i=e[i].next)

const int MAXN=5005;
const int MAXM=5e4+5;
const int D=1e8;
const int oo=0x3f3f3f3f;

int N,M,cst[MAXN],S,T,ans=0,d[MAXN];
struct cust{
    int x,y,v;
}c[MAXM];
bool vis[MAXN];

namespace Maxflow{
    struct edge{
        int y,next,flow,rev;
    }e[(MAXM+MAXN)<<2];
    int LINK[MAXN],len=0,level[MAXN];
    deque<int>q;
    inline void ins(int x,int y,int flow,int rev){
        e[++len].next=LINK[x];LINK[x]=len;
        e[len].y=y;e[len].flow=flow;e[len].rev=len+rev;
    }
    inline void Ins(int x,int y,int flow){
        ins(x,y,flow,1);
        ins(y,x,0,-1);
        //printf("%d %d %d\n",x,y,flow==oo?-1:flow);
    }
    bool makelevel(){
        fill(level+1,level+T+1,-1);
        q.push\_back(S);level[S]=0;
        while(!q.empty()){
            int node=q.front();q.pop\_front();
            Auto(i,node)if(level[e[i].y]==-1&&e[i].flow){
                level[e[i].y]=level[node]+1;
                q.push\_back(e[i].y);
            }
        }
        return level[T]!=-1;
    }
    int addflow(int node,int flow){
        if(!flow||node==T)return flow;
        int maxflow=0,d;
        Auto(i,node)if(level[e[i].y]==level[node]+1&&e[i].flow)
            if(d=addflow(e[i].y,min(e[i].flow,flow-maxflow))){
                e[i].flow-=d;
                e[e[i].rev].flow+=d;
                maxflow+=d;
            }
        if(!maxflow)level[node]=-1;
        return maxflow;
    }
    void Dinic(){
        int d;
        while(makelevel())
            while(d=addflow(S,oo))
                ans+=d;
    }
    void DFS(int node){
        vis[node]=1;
        Auto(i,node)if(e[i].flow&&!vis[e[i].y])
            DFS(e[i].y);
    }
}using namespace Maxflow;

namespace solution{
    void Prepare(){
        scanf("%d%d",&N,&M);
        up(i,1,N)scanf("%d",&cst[i]);
        up(i,1,M){
            scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].v);
            d[c[i].x]+=c[i].v;
            d[c[i].y]+=c[i].v;
        }
    }
    void Solve(){
        S=N+1;T=N+2;
        up(i,1,M){
            Ins(c[i].x,c[i].y,c[i].v);
            Ins(c[i].y,c[i].x,c[i].v);
        }    
        up(i,1,N){
            Ins(S,i,D);
            Ins(i,T,2*cst[i]-d[i]+D);
        }
        Dinic();
        Auto(i,S)if(e[e[i].rev].flow)ans-=D;
        ans=-ans;
        ans/=2;
        printf("%d\n",ans);
    }
}

int main(){
    using namespace solution;
    Prepare();
    Solve();
    return 0;
}