「SNOI2019」通信

传送门

Description

\(n\)个排成一列的哨站要进行通信。第\(i\)个哨站的频段为\(a_i\)。

每个哨站\(i\)需要选择以下二者之一：

1. 直接连接到控制中心，代价为\(W\)；
2. 连接到前面的某个哨站\(j\ (j<i)\)，代价为\(|a_j-a_i|\)。

每个哨站只能被后面的至多一个哨站连接。

请你求出最小可能的代价和。

Description

很容易想到一种最小费用最大流的模型

把每个点拆成\(x_i\)和\(y_i\)

对于每个\(i\)，连边

1. \(S\rightarrow x_i :w=1,c=0\)
2. \(S \rightarrow y_i:w=1,c=W\)
3. \(y_i \rightarrow T :w=1,c=0\)
4. \(x_i\rightarrow y_j \ (j>i) :w=1,c=|a_i-a_j|\)

这样，边数\(O(n^2)\)，点数\(O(n)\)，显然是不行的

考虑优化中间部分的连边

我们建立一个分治的过程，对于当前，考虑\(x\)的下标为\([l,mid]\)到\(y\)的下标为\([mid+1,r]\)的连边

分别处理形如\(a_i-a_j (i>j)\)和\(a_j-a_i (i>j)\)的两种情况的边，它们的处理方式相似

如何处理第一种情况？

把\(a_l\)~\(a_{mid}\)的值离散化后，新建表示这些值的节点，从大到小把这些点连接成为一个链

使用类似前后缀优化建图的方式

将\(x_l\)~\(x_{mid}\)连接到链的适当位置，其中\(w=1,c=a_i\)

链的适当位置向\(y_{mid+1}\)~\(y_r\)连边，其中\(w=1,c=-a_j\)

Code?

#include<bits/stdc++.h>
#define dbg1(x) cerr<<#x<<"="<<(x)<<" "
#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"
#define dbg3(x) cerr<<#x<<"\n"
#define M(x,y) memset(x,y,sizeof x)
#define ll long long
using namespace std;
#define reg register
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
const int N=12005,inf=1e9;
class Flow
{
    bool vis[N],inq[N];ll dis[N];queue<int>q;
    struct edge{int to,w,c,nex;}e[N*10];int cur[N],hr[N],en;
    bool spfa()
    {
        for(int i=S;i<=T;++i) cur[i]=hr[i],inq[i]=0,dis[i]=1e18;
        for(dis[S]=0,inq[S]=1,q.push(S);!q.empty();)
        {
            int u=q.front();q.pop(),inq[u]=0;
            for(int i=hr[u];i;i=e[i].nex)
            if(dis[e[i].to]>dis[u]+e[i].c&&e[i].w)
            {
                dis[e[i].to]=dis[u]+e[i].c;
                if(!inq[e[i].to]) inq[e[i].to]=1,q.push(e[i].to);
            }
        }
        return dis[T]<inf;
    }
    int dfs(int x,int f)
    {
        if(x==T||!f) return f;vis[x]=1;
        int w,used=0;
        for(int &i=cur[x];i;i=e[i].nex)
        if(dis[e[i].to]==dis[x]+e[i].c&&e[i].w&&!vis[e[i].to])
        {
            w=dfs(e[i].to,min(f-used,e[i].w));
            e[i].w-=w;e[i^1].w+=w;used+=w;
            if(used==f) break;
        }
        vis[x]=0;return used;
    }
    public:
        int S,T;
        Flow(){S=0;en=1;}
        void ins(int x,int y,int w,int c)
        {   dbg1(x);dbg2(y);
            e[++en]=(edge){y,w,c,hr[x]},hr[x]=en;
            e[++en]=(edge){x,0,-c,hr[y]},hr[y]=en;
        }
        ll Ans(){ll r=0;while(spfa())r+=dfs(S,inf)*dis[T];return r;}
}F;
int n,W,a[N],ar[N],tot;
void Solve(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1,tt,i,j;
    #define lb(x) lower_bound(ar+1,ar+1+tt,x)-ar
    #define p(x) tot+x

    for(tt=0,i=l;i<=mid;++i) ar[++tt]=a[i];
    sort(ar+1,ar+tt+1);tt=unique(ar+1,ar+tt+1)-ar-1;
    for(i=2;i<=tt;++i) F.ins(p(i),p(i-1),inf,0);
    for(i=l;i<=mid;++i) F.ins(i,p(lb(a[i])),1,a[i]);
    for(i=mid+1;i<=r;++i) if((j=lb(a[i]))<=tt) F.ins(p(j),i+n,1,-a[i]);
    tot+=tt;
    
    for(tt=0,i=mid+1;i<=r;++i) ar[++tt]=a[i];
    sort(ar+1,ar+tt+1);tt=unique(ar+1,ar+tt+1)-ar-1;
    for(i=2;i<=tt;++i) F.ins(p(i-1),p(i),inf,0);
    for(i=l;i<=mid;++i) if((j=lb(a[i]))<=tt) F.ins(i,p(j),1,-a[i]);
    for(i=mid+1;i<=r;++i) F.ins(p(lb(a[i])),i+n,1,a[i]);
    tot+=tt;
    
    Solve(l,mid);Solve(mid+1,r);
}
int main()
{
    tot=(n=read())<<1,W=read();
    reg int i;
    for(i=1;i<=n;++i) a[i]=read();
    Solve(1,n);F.T=tot+1;
    for(i=1;i<=n;++i) F.ins(F.S,i,1,0),F.ins(F.S,i+n,1,W),F.ins(i+n,F.T,1,0);
    printf("%lld\n",F.Ans());
}

Blog来自PaperCloud，未经允许，请勿转载，TKS！