题解 P3831 【[SHOI2012]回家的路】

Peipei
还是我的logo ^_^


这个题乍一看像个网络流
然而不是
然后就发现特别像最短路的题

把每一行的点互相连边,每一列同理
每次转移时判断当前点是不是转折点,一次判断是否+1

但是有一点让这道题不像最短路:

如果一条线上全是转折点,那岂不是边的条数要达到

n^2 !!!

但是我们发现有些边是没必要建的,比如 A -> B -> C
那么我们就没必要建一条 A -> C 的边了
所以我们把相邻的建边,spfa 飞过就好了

但是有个小细节,就像 A -> B -> C 中 B 不能算作转折点
在 B 处不 +1
至于如何判断当前点是否为转折点
我们记录当前点的 fa[x]
判断 如果 fa[x] 与 go(即将转移的点) 不共线, 那么 x 就是一个转折点


#include <bits/stdc++.h>
#define II int
#define IL inline
#define R register
#define I 423546
using namespace std;

IL void of(R II &a) {
    R char c=getchar (); R II w=1, p=0;
    while (c<'0' || c>'9') { if(c=='-') w=-1; c=getchar (); }
    while (c>='0' && c<='9') { p=p*10+c-'0'; c=getchar (); }
    a=w*p;
}

/* -------------------- Peipei -------------------- */

II n,m,_tot;
II head[I], dis[I], inq[I], fa[I];
queue <II> Q;

struct oAo { II x,y,wei; } edge[I];
IL bool maPx(oAo a1,oAo a2) { return a1.x==a2.x ? a1.y<a2.y : a1.x<a2.x ;}
IL bool maPy(oAo a1,oAo a2) { return a1.y==a2.y ? a1.x<a2.x : a1.y<a2.y ;}
IL bool maPwei(oAo a1,oAo a2) { return a1.wei<a2.wei ;}

struct owo { II to,up,w; } aa[I];
IL void add(R II x,R II y,R II z) {
    aa[++_tot]=(owo) {y,head[x],z};
    head[x]=_tot;
}

IL void spfa() {
    for(R II i=1;i<=m+1;i++) dis[i]=1e9;
    Q.push(0); inq[0]=1; dis[0]=0;
    while (!Q.empty()) {
        R II x=Q.front(); Q.pop(); inq[x]=0;
        for(R II i=head[x],go,K;i;i=aa[i].up)
        {
            go=aa[i].to; 
            K=(edge[fa[x]].x!=edge[go].x && edge[fa[x]].y!=edge[go].y);
            if(dis[go]>dis[x]+aa[i].w+K) {
                dis[go]=dis[x]+aa[i].w+K;
                if(!inq[go]) Q.push(go), inq[go]=1;
                fa[go]=x;
            }
        }
    }
    printf("%d\n",dis[m+1]);
    exit(0);
}

int main()
{
    of(n); of(m);
    for(R II i=1;i<=m;i++) 
        of(edge[i].x), of(edge[i].y), edge[i].wei=i;
    of(edge[0].x); of(edge[0].y);
    of(edge[m+1].x); of(edge[m+1].y); 
    edge[m+1].wei=m+1;

    sort(edge,edge+m+2,maPx);
    for(R II i=0;i<=m;i++) 
        if(edge[i].x==edge[i+1].x) {
            add(edge[i].wei,edge[i+1].wei,abs(edge[i].y-edge[i+1].y)*2);
            add(edge[i+1].wei,edge[i].wei,abs(edge[i].y-edge[i+1].y)*2);
        }
    sort(edge,edge+m+2,maPy);
    for(R II i=0;i<=m;i++) 
        if(edge[i].y==edge[i+1].y) {
            add(edge[i].wei,edge[i+1].wei,abs(edge[i].x-edge[i+1].x)*2);
            add(edge[i+1].wei,edge[i].wei,abs(edge[i].x-edge[i+1].x)*2);
        }
    sort(edge,edge+m+2,maPwei);

    spfa();
}


发表于 2018-02-24 15:30:24 in 题解