题解 P4667 【[BalticOI 2011 Day1]Switch the Lamp On】

WorldBest丶牛顿 · 2018-09-12 01:04:18 · 题解

注意这篇题解有四份代码，AC代码需要您们拼凑一下qwq

对于原来的电路来说，我们可以将每个顶点和它周围的点相连
点之间存在导线的两个点连一条边权为 0 的边，不存在导线的连一条边权为 1 的边
为什么这么做呢，原来有边的两个点本来就是通路的，也就不需要加边权
原来没有边的两个点，需要将导线转一下，那转动导线的操作也就是经过一条边权为 1 的边，最短路的长度加 1

这样就能将这道题转化为一个求从左上角到右下角的最短路的题目
很明显这是一个网格图，而且时限 150ms 最好不要用某个算法

我先是写了一个优先队列优化的 Dijkstra（开了 O2 过了，不开 80-90 左右）

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;

const int INF=19260817;
int n,m,cnt,sum;
int left_up,left_down,right_up,right_down;
char f[505];
int head[1100001],d[1100001];

struct edge
{
    int next,w,v;
}e[1100001];

void add(int u,int v,int w)
{
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}

struct node
{
    int u,d;
    bool operator<(const node& rhs) const{
        return d>rhs.d;
    }
}; //用cmp的写法wa了一个晚上之后我就再也不那么写了

void Dijkstra()
{
    sum=(m+1)*(n+1);//这是总的节点数
    priority_queue<node> q;
    for(int i=1;i<=sum;i++) d[i]=INF;
    d[1]=0;
    q.push((node){1,d[1]});
    while(!q.empty())
    {
        node x=q.top(); q.pop();
        int u=x.u;
        if(x.d!=d[u]) continue;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].v,w=e[i].w;
            if(d[u]+w<d[v])
            {
                d[v]=d[u]+w;
                q.push((node){v,d[v]});
            }
        }
    }
    if(d[sum]==INF) cout<<"NO SOLUTION";
    else cout<<d[sum];
} 

int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<n;++i)
    {
        cin>>f;
        for(int j=0;j<m;++j)
        {
            left_up=(m+1)*i+j+1;
            right_up=(m+1)*i+j+2;
            left_down=(m+1)*(i+1)+j+1;
            right_down=(m+1)*(i+1)+j+2;
            //处理节点编号，一条边占一个格子的话就会有四个顶点
            if(f[j]==92)//不知道转义符的我就只能写个ASCII码了
            {
                add(left_up,right_down,0);
                add(right_down,left_up,0);//无向图正反存一次
                add(left_down,right_up,1);
                add(right_up,left_down,1);
            }
            if(f[j]==47)
            {
                add(left_down,right_up,0);
                add(right_up,left_down,0);
                add(left_up,right_down,1);
                add(right_down,left_up,1);
            }
        }
    }
    Dijkstra();
    return 0;
}

虽然过了，但是这种方法肯定是不完美的（毕竟开 O2 才行）。
很明显，我这个存图的方式常数太大，那我们可以改一下存图

void add(int u,int v,int w)
{
    e[++cnt].v=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;
    e[++cnt].v=u;e[cnt].w=w;e[cnt].next=head[v],head[v]=cnt;
}//顺便也改一下，写起来更加方便了

//main函数中的存图
    for(int i=1;i<=n+1;++i)
        for(int j=1;j<=m+1;++j)
            mark[i][j]=++tot;//预处理出每个顶点的编号
    for(int i=1;i<=n;++i)
    {
        cin>>f;
        for(int j=1;j<=m;++j)
        {
            if(f[j-1]=='/')
            {
                add(mark[i][j],mark[i+1][j+1],1);//调整一下存图函数就方便了很多
                add(mark[i+1][j],mark[i][j+1],0);
            }
            else
            {
                add(mark[i][j],mark[i+1][j+1],0);
                add(mark[i+1][j],mark[i][j+1],1);
            }
        }
    }

但是这种写法还是只有 90 分左右，那该怎么办呢？
注意到 Dijkstra 的堆优化中会重复加点很多次
在 Dijkstra 中，我们明明只是需要找出 dis 值最小的点不是吗

那我们就可以使用线段树来优化查询操作（只需要单点修改呢）
只要最初将值都设为 INF ，起点设为 0 ，线段树储存最小值，
将走过的点也设为 INF ， Dijkstra 的时候判断树根的值是否等于 INF ，
如果等于的话就没有点能更新了，就做完了
可以看一下告诉我这个方法的 @yizimi远欣大佬的博客

struct segment_tree
{
    int minx[1100001],tag[1100001];
    void push_up(int p)
    {
        minx[p]=min(minx[p<<1],minx[p<<1|1]);
        tag[p]=(minx[p<<1]<minx[p<<1|1])?tag[p<<1]:tag[p<<1|1];
        //minx存最小值，tag存拥有这个值的点的编号
    }
    void build(int l,int r,int p)
    {
        if(l==r)
        {
            minx[p]=d[l];
            tag[p]=l;
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,p<<1);
        build(mid+1,r,p<<1|1);
        push_up(p);
    }
    void update(int now,int l,int r,int p,int k)
    {
        if(l==r)
        {
            minx[p]=k;
            return;
        }
        int mid=(l+r)>>1;
        if(now<=mid) update(now,l,mid,p<<1,k);
        else update(now,mid+1,r,p<<1|1,k);
        push_up(p);
    }
}tree;

void Dijkstra()
{
    for(int i=2;i<=tot;i++) d[i]=INF;
    tree.build(1,tot,1);
    while(tree.minx[1]<INF)//如果线段树的树根的值为INF，那所有能找的点都找完了
    {
        int u=tree.tag[1];
        tree.update(u,1,tot,1,INF);//走过的点设为INF，相当于vis数组
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].v,w=e[i].w;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                tree.update(v,1,tot,1,d[v]);//树上更新
            }
        }
    }
    if(d[tot]==INF) cout<<"NO SOLUTION";
    else cout<<d[tot];
}

为什么还是过不了啊，递归线段树的常数这么大吗 qwq
等一下，我们只需要单点修改，查询都不用
那我们为什么不写一棵常数很小，代码又短的zkw线段树呢

struct segment_tree
{
    int bit;
    int minx[1100001],tag[1100001];//真的是习惯了写sum，当成最小值看就行了
    void push_up(int n)
    {
        minx[n]=min(minx[n<<1],minx[n<<1|1]);
        tag[n]=minx[n<<1]<minx[n<<1|1]?tag[n<<1]:tag[n<<1|1];
    }
    void build(int n)
    {
        for(bit=1;bit<=n+1;bit<<=1);
        for(int i=bit+1;i<=(bit<<1)-1;++i)
        {
             //注意这里结束循环的条件为(bit<<1)-1，这是因为zkw线段树需要把叶子填满，
             //如果不填满的话最后就会有编号大于n的点值为0，树根始终为0，陷入死循环
             minx[i]=i-bit==1?0:INF;//将出发点的dis值设为0
             tag[i]=i-bit;
        }
        for(int i=bit-1;i>=1;--i)
            push_up(i);
    }
    void update(int n,int k)
    {
        for(minx[n+=bit]=k,n>>=1;n;n>>=1)
            push_up(n);
    }
}tree;

至此，就可以满分通关啦！

题解 P4667 【[BalticOI 2011 Day1]Switch the Lamp On】

注意 这篇题解有四份代码，AC代码需要您们拼凑一下qwq

注意这篇题解有四份代码，AC代码需要您们拼凑一下qwq