题解 P3831 【[SHOI2012]回家的路】
wuzhoupei
2018-02-24 15:30:24
还是我的**logo** ^_^
-----
这个题乍一看像个网络流
然而不是
然后就发现特别像最短路的题
把每一行的点互相连边，每一列同理
每次转移时判断当前点是不是转折点，一次判断是否+1
但是有一点让这道题不像最短路：
### 如果一条线上全是转折点，那岂不是边的条数要达到
# n^2 !!!
但是我们发现有些边是没必要建的，比如 A -> B -> C
那么我们就没必要建一条 A -> C 的边了
所以我们把相邻的建边，spfa 飞过就好了
但是有个小细节，就像 A -> B -> C 中 B 不能算作转折点
在 B 处不 +1
至于如何判断当前点是否为转折点
我们记录当前点的 fa[x]
判断 如果 fa[x] 与 go(即将转移的点) 不共线， 那么 x 就是一个转折点
--------------
```cpp
#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();
}
```
----------