M_sea

洛谷5331 [SNOI2019]通信
LuoguLOJ分析先考虑一个暴力的费用流做法。把每个哨站拆成两个点 $i_1$ 和 $i_2$ 。然后这样连边:...
扫描右侧二维码阅读全文
01
2019/05

洛谷5331 [SNOI2019]通信

Luogu

LOJ

分析

先考虑一个暴力的费用流做法。

把每个哨站拆成两个点 $i_1$ 和 $i_2$ 。

然后这样连边:

  • $s$ 向 $i_1$ 连容量为 $1$ 、费用为 $0$ 的边, $i_2$ 向 $t$ 连容量为 $1$ 、费用为 $0$ 的边。
  • $i_1$ 向 $t$ 连容量为 $1$ 、费用为 $W$ 的边。
  • 对于每个 $j<i$ ,$i_1$ 向 $j_2$ 连容量为 $1$ 、费用为 $|a_i-a_j|$ 的边。

最小费用就是答案。

但是这样的边数是 $n^2$ 级别的,可以获得 $80$ 分的好成绩。

考虑减少边数。直接分治/主席树优化连边就可以把边数优化到 $n\log n$ 级别了。然后就可以过了。

具体实现及细节见代码。

代码

80pt

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;

int n,W,s,t;
int a[N];

struct Edge { int v,w,c,nxt; } e[1000010];
int head[100010];

inline void addEdge(int u,int v,int w,int c) {
    static int cnt=2;
    e[cnt]=(Edge){v,w,c,head[u]},head[u]=cnt++;
    e[cnt]=(Edge){u,0,-c,head[v]},head[v]=cnt++;
}

ll dis[100010];
int inq[100010],lst[100010];

inline int spfa() {
    for (re int i=s;i<=t;++i) dis[i]=1e18,inq[i]=0,lst[i]=0;
    queue<int> Q; Q.push(s); dis[s]=0,inq[s]=1;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if (e[i].w&&dis[u]+e[i].c<dis[v]) {
                dis[v]=dis[u]+e[i].c,lst[v]=i;
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
    return lst[t]!=0;
}
int main() {
    n=read(),W=read(),s=0,t=2*n+1;
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=n;++i) addEdge(s,i,1,0),addEdge(i+n,t,1,0);
    for (re int i=1;i<=n;++i) {
        addEdge(i,t,1,W);
        for (re int j=1;j<i;++j) addEdge(i,j+n,1,abs(a[i]-a[j]));
    }
    ll ans=0;
    while (spfa()) {
        int f=1e9;
        for (re int i=lst[t];i;i=lst[e[i^1].v]) f=min(f,e[i].w);
        for (re int i=lst[t];i;i=lst[e[i^1].v]) e[i].w-=f,e[i^1].w+=f;
        ans+=f*dis[t];
    }
    printf("%lld\n",ans);
    return 0;
}

100pt

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;

int n,W,s,t;
int a[N];

struct Edge { int v,w,c,nxt; } e[1000010];
int head[100010];

inline void addEdge(int u,int v,int w,int c) {
    static int cnt=2;
    e[cnt]=(Edge){v,w,c,head[u]},head[u]=cnt++;
    e[cnt]=(Edge){u,0,-c,head[v]},head[v]=cnt++;
}

ll dis[100010];
int inq[100010],lst[100010];

inline int spfa() {
    memset(dis,0x3f,sizeof(dis)),memset(lst,0,sizeof(lst));
    queue<int> Q; Q.push(s); dis[s]=0,inq[s]=1;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if (e[i].w&&dis[u]+e[i].c<dis[v]) {
                dis[v]=dis[u]+e[i].c,lst[v]=i;
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
    return lst[t]!=0;
}

int S[N],tot=0;

inline void build(int l,int r) {
    if (l==r) return;
    int mid=(l+r)>>1,m=0;
    for (re int i=l;i<=r;++i) S[++m]=a[i];
    sort(S+1,S+m+1); m=unique(S+1,S+m+1)-S-1;
    for (re int i=1;i<m;++i) {
        addEdge(tot+i,tot+i+1,1e9,S[i+1]-S[i]);
        addEdge(tot+i+1,tot+i,1e9,S[i+1]-S[i]);
    }
    for (re int i=l;i<=r;++i) {
        int p=lower_bound(S+1,S+m+1,a[i])-S;
        if (i<=mid) addEdge(i,tot+p,1,0);
        else addEdge(tot+p,i+n,1,0);
    }
    tot+=m,build(l,mid),build(mid+1,r);
}

int main() {
    n=read(),W=read(),s=0,t=tot=2*n+1;
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=n;++i)
        addEdge(s,i,1,0),addEdge(i,t,1,W),addEdge(i+n,t,1,0);
    build(1,n);
    ll ans=0;
    while (spfa()) {
        int f=1e9;
        for (re int i=lst[t];i;i=lst[e[i^1].v]) f=min(f,e[i].w);
        for (re int i=lst[t];i;i=lst[e[i^1].v]) e[i].w-=f,e[i^1].w+=f;
        ans+=f*dis[t];
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 10 : 02 PM

发表评论