AFO

题解 P5100 【[JOI 2017 Final]足球】

2020-11-06 10:48:23


注意到每个人至多控球一次,那么球一定是一个人控着到某个地方,然后一脚踢出去,然后一个最近的球员跑过来控球并重复以上过程。

可以考虑建图跑最短路,但是这个代价长得比较奇妙,因此我们也需要一些奇妙的建图。

注意到控球时可以上下左右跑,但是球一旦被踢出去就只能往一个方向前进;还注意到可以把那个 $Ap+B$ 看成先变成未被控球花费 $B$,然后滚动 $1$ 米花费 $A$。这些启发我们拆点。

下面的题解都拆了 $6$ 个点,其实只要拆成 $3$ 个点就好了。对于每个点我们拆出 $3$ 个点表示控球($0$)、未被控球左右滚动($1$)、未被控球上下滚动($2$)。

然后大概有这样几类边要连($dis_{i,j}$ 表示距离 $(i,j)$ 最近的球员到 $(i,j)$ 的距离(当然是指曼哈顿距离)):

  • $(i,j,0)$ 向四周的 $0$ 连边权为 $C$ 的边,表示控球跑 $1$ 米。
  • $(i,j,1)$ 向左右的 $1$ 连边权为 $A$ 的边,表示球向左右滚动 $1$ 米。
  • $(i,j,2)$ 向上下的 $2$ 连边权为 $A$ 的边,表示球向上下滚动 $1$ 米。
  • $(i,j,0)$ 向 $(i,j,1)$ 和 $(i,j,2)$ 连边权为 $B$ 的边,表示把球踢出去。
  • $(i,j,1)$ 和 $(i,j,2)$ 向 $(i,j,0)$ 连边权为 $dis_{i,j}\times C$ 的边,表示最近的球员跑过来把球控住。

然后跑最短路即可。

我也不知道为啥跑得比拆 6 个点的 kls 慢那么多,可能是因为他太强了。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

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=100000+10,M=500+10;
const int V=1000000+10,E=9000000+10;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int w,h,a,b,c,n,x[N],y[N];

namespace H {
    queue<pair<int,int>> Q;
    int dis[M][M];
    void bfs() {
        memset(dis,0x3f,sizeof(dis));
        for (int i=1;i<=n;++i)
            dis[x[i]][y[i]]=0,Q.push({x[i],y[i]});
        while (!Q.empty()) {
            int x=Q.front().first,y=Q.front().second; Q.pop();
            for (int d=0;d<4;++d) {
                int X=x+dx[d],Y=y+dy[d];
                if (X<0||X>w||Y<0||Y>h) continue;
                if (dis[x][y]+1<dis[X][Y])
                    dis[X][Y]=dis[x][y]+1,Q.push({X,Y});
            }
        }
    }
}

int id[M][M][3],tot=0;
struct edge { int v; ll w; int nxt; } e[E];
int head[V];
void addEdge(int u,int v,ll w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}

struct node { int u; ll d; };
bool operator <(node a,node b) { return a.d>b.d; }
priority_queue<node> Q; 
ll dis[V];
void dijkstra(int s) {
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0,Q.push((node){s,0});
    while (!Q.empty()) {
        int u=Q.top().u; ll d=Q.top().d; Q.pop();
        if (d!=dis[u]) continue;
        for (int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; ll w=e[i].w;
            if (dis[u]+w<dis[v])
                dis[v]=dis[u]+w,Q.push((node){v,dis[v]});
        }
    }
}

int main() {
    w=read(),h=read(),a=read(),b=read(),c=read(),n=read();
    for (int i=1;i<=n;++i) x[i]=read(),y[i]=read();
    H::bfs();
    for (int i=0;i<=w;++i)
        for (int j=0;j<=h;++j)
            for (int k=0;k<3;++k) id[i][j][k]=++tot;
    for (int i=0;i<=w;++i)
        for (int j=0;j<=h;++j) {
            addEdge(id[i][j][0],id[i][j][1],b);
            addEdge(id[i][j][0],id[i][j][2],b);
            addEdge(id[i][j][1],id[i][j][0],1ll*H::dis[i][j]*c);
            addEdge(id[i][j][2],id[i][j][0],1ll*H::dis[i][j]*c);
            for (int d=0;d<4;++d) {
                int x=i+dx[d],y=j+dy[d];
                if (x<0||x>w||y<0||y>h) continue;
                addEdge(id[i][j][0],id[x][y][0],c);
                if (d==1||d==3) addEdge(id[i][j][1],id[x][y][1],a);
                else addEdge(id[i][j][2],id[x][y][2],a);
            }
        }
    dijkstra(id[x[1]][y[1]][0]);
    ll ans=1e18;
    ans=min(ans,dis[id[x[n]][y[n]][0]]);
    ans=min(ans,dis[id[x[n]][y[n]][1]]);
    ans=min(ans,dis[id[x[n]][y[n]][2]]);
    printf("%lld\n",ans);
    return 0;
}