题解 P2296 【寻找道路】

milk_candy · 2019-10-27 16:47:36 · 题解

题意分析

给一个有向图，每条边的连边长度都是1。
再给出起点、终点，让您找出起点到终点的最短路径，但这个最短路径必须满足：你找的那个路径上的所有点，每个点的所有连接的点都要“能去终点”，不然就不条件。
我们就拿样例这个图来分析一下，
，在这里，2是不能选在路径里面的，因为 2所有连接的点有 5 和 6，而6是不能去终点5的。
故2不能被选去路径里面。

解题思路

[考场思路，非最简解法]。看到题面里面已经说了“最短距离”，外加这里已经是单个起点，马上想到了“单源最短路径”。
再看点的个数\leq 10000，应该不会超过“单源最短路径”所能处理的数据规模。
于是，我的解题思路就是：“堆优Dij”。
但是这里路径是特殊的，我们不能把那些不合法的点拉进去。于是我决定开一个布尔数组BlackList，用来记录哪些点是不合法的，这些点是绝对不能拉进路径里面的。

Prob.1 判断不合法

不难发现，如果一个点不合法，则
- 这个点没有出度。（6没有出度，6很显然不能被加到路径里面的。）
- 这个点不是终点。（5没有出度，但是5不是不合法。）
那一开始我们读入完之后，就需要把这些个不合法的点拉进 BlackList，然后再进行“删点”后的堆优 Dijkstra。
这里为了存储一个点的父亲都是些谁，我们就需要反向存边了。
比如1连接到2，我们要记录2的父亲有一个是1（G[2].push_back(1);）
然后直接从1到n，for循环判断这些点是否无出度 && 非终点，如果是，则i和i的所有父亲(G[i]所有)是不合法的，拉入黑名单。
用链式前向星存图的时候，判断一个点i是否出度为0，只需要判断front[i]是否为你赋的初始值（一般是-1）。如果front又-1，这个点又不是终点，那么直接判断这个点及其所有父亲是不合法的。
用链式前向星存图，并用vector<int> G[i]存储i的所有父亲节点编号的“判断不合法”代码段如下：

for(int i=1;i<=n;i++)
{
  if(front[i]==-1&&i!=End)  //既出度为0，又不是终点
  {
      BlackList[i]=true;    //自身拉进黑名单
      for(int j=0;j<G[i].size();j++)
          BlackList[G[i][j]]=true;  //及其父亲被拉进黑名单
  }
}

Prob.2 堆优Dij

现在就是要做以起点为源点，到终点（但不能去不合法的点）的最短路径。
没问题的话，那我们直接上堆优Dij就行了。如果不懂堆优Dij，堆优Dij的裸题就是P4779可以做做~。
下面就是堆优Dij的主体代码，

while(!Q.empty())
{
  HeapNode x=Q.top();
  int u=x.u;

  if(x.d>dis[u])
      continue;

  Q.pop();
  for(int i=front[u];i!=-1;i=E[i].nxt)//遍历当前点所有连接的点
      if(!BlackList[E[i].to])           //黑名单的限制
      {
          int v=E[i].to;
          if(dis[u]+1<dis[v])
          {
              dis[v]=dis[u]+1;
              Q.push((HeapNode){v,dis[v]});
          }
      }
}

可以发现，这个堆优Dij和普通的堆优Dij的区别就是这个在遍历当前点所有连接的点的时候，加入了黑名单的限制（即加入了BlackList的点不可以被遍历到）
边长为1。就这样，我们删除不合法的点之后，可以开始堆优Dij了。最后输出dis[终点]就可。

参考程序

#include<queue>
#include<vector>
#include<stdio.h>
using namespace std;

int n,m,x,y,Start,End,cnt;

int front[10005];
struct OneEdge
{
    int to,nxt;
} E[200005];
inline void add(int x,int y)
{
    cnt++;
    E[cnt].to=y;
    E[cnt].nxt=front[x];
    front[x]=cnt;
}                       //链式前向星建边，边长都为1这里不记录边长了。

bool BlackList[10005];  //黑名单的限制

vector<int> G[10005];

int dis[10005];

//堆优dij↓
struct HeapNode
{
    int u,d;
};
bool operator <(const HeapNode& now,const HeapNode& rhs)
{
    return now.d>rhs.d;
}
priority_queue<HeapNode> Q;

void Dijkstra()
{
    for(int i=1;i<=n;i++)
        dis[i]=987654321;
    dis[Start]=0;

    int u,d;
    Q.push((HeapNode){Start,0});
    while(!Q.empty())
        {
            HeapNode x=Q.top();
            int u=x.u;

            if(x.d>dis[u])
                continue;

            Q.pop();
            //拉出，后遍历所有连边
            for(int i=front[u];i!=-1;i=E[i].nxt)
                 if(!BlackList[E[i].to])
                    {
                        int v=E[i].to;
                        if(dis[u]+1<dis[v])
                            {
                                dis[v]=dis[u]+1;
                                Q.push((HeapNode){v,dis[v]});
                            }
                    }
        }

}
//堆优Dij↑

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        front[i]=-1;
    for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            add(x,y);
            G[y].push_back(x);
        }
    scanf("%d%d",&Start,&End);

    for(int i=1;i<=n;i++)
        {
            if(front[i]==-1&&i!=End)
                {
                    BlackList[i]=true;
                    for(int j=0;j<G[i].size();j++)
                        BlackList[G[i][j]]=true;
                }
        }

    Dijkstra();
    printf("%d",dis[End]==987654321?-1:dis[End]);
    return 0;
}

G数组记录每个点的父亲都是些哪些点。
使用链式前向星建图（每条边中都有一个nxt）。

解题反思

没有想到简单解决方法，下次要一下把最优解找到就好了