洛谷4542 [ZJOI2011]营救皮卡丘

Luogu

BZOJ

分析

先预处理出 $dis[i][j]$ ,表示在不经过编号大于 $\max\{i,j\}$ 的点的情况下, $i$ 到 $j$ 的最短路。显然可以用 $\mathrm{Floyd}$ 做。

考虑每个人破坏掉的据点构成的序列。

如果把 $0$ 号点加到每个人的序列开头,那么每个人经过的边的和就是 $\sum\limits_{i=1}^{m-1} dis[i][i+1]$ ,其中 $m$ 是序列的长度。

于是问题等价于,用 $k$ 条路径覆盖一张图,其中边 $(u,v)$ 的边权是 $dis[u][v]$。

考虑用费用流来解决这个问题。将每个点拆成入点 $s_i$ 和出点 $t_i$ 。考虑怎么连边:

  • 从源点向 $s_0$ 连容量为 $k$ 、费用为 $0$ 的边,表示 $k$ 条路径。
  • 从源点向 $s_i\ (i\neq 1)$ 连容量为 $1$ 、费用为 $0$ 的边。
  • 从 $t_i\ (i\neq 1)$ 向汇点连容量为 $1$ 、费用为 $0$ 的边。
  • 从 $s_i$ 向 $t_j\ (j>i)$ 连容量为 $1$ 、费用为 $dis[i][j]$ 的边。

最小费用就是答案。

代码

代码中把所有数的下标加了 $1$ ,也就是 $0$ 号点变成了 $1$ 号点。

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
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;
}

int n,m,K,s,t;
int dis[200][200];

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++;
}

int d[100010],inq[100010],last[100010];

inline int spfa() {
    memset(last,0,sizeof(last));
    memset(d,0x3f,sizeof(d)); d[s]=0;
    queue<int> Q; Q.push(s); 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&&d[u]+e[i].c<d[v]) {
                d[v]=d[u]+e[i].c,last[v]=i;
                if (!inq[v]) Q.push(v),inq[v]=1;
            }
        }
    }
    return last[t]!=0;
}

int main() {
    n=read()+1,m=read(),K=read(),s=0,t=n*2+1;
    memset(dis,0x3f,sizeof(dis));
    for (re int i=1;i<=n;++i) dis[i][i]=0;
    for (re int i=1;i<=m;++i) {
        int u=read()+1,v=read()+1,w=read();
        dis[u][v]=dis[v][u]=min(dis[u][v],w);
    }
    
    for (re int k=1;k<=n;++k)
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=n;++j) {
                if (k>i&&k>j) continue;
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }

    addEdge(s,1,K,0);
    for (re int i=2;i<=n;++i) addEdge(s,i,1,0),addEdge(i+n,t,1,0);
    for (re int i=1;i<=n;++i)
        for (re int j=i+1;j<=n;++j)
            addEdge(i,j+n,1,dis[i][j]);

    int ans=0;
    while (spfa()) {
        int f=2e9;
        for (re int i=last[t];i;i=last[e[i^1].v]) f=min(f,e[i].w);
        for (re int i=last[t];i;i=last[e[i^1].v]) e[i].w-=f,e[i^1].w+=f;
        ans+=f*d[t];
    }
    printf("%d\n",ans);
        
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 23 PM

发表评论