华师一附中OI组

标题: 路由选择 [打印本页]

作者: admin 时间: 2018-4-16 11:50
标题: 路由选择
在网络通信中，经常需要求最短路径。但完全用最短路径传输有这样一个问题：如果最终在两个终端节点之间给出的最短路径只有一条。则在该路径中的任一个节点或链路出现故障时，信号传输将面临中断的危险。因此，对网络路由选择作了以下改进：
为任意两节点之间通信提供三条路径供其选择，即最短路径、第二最短路径和第三最短路径。
第一最短路径定义为：给定一个不含负回路的网络D={V，A，W}，其中V={v1，v2，…，vn}，A 为边的集合，W 为权的集合，设P1 是D 中最短（v1，vn）路。称P1 为D 中最短（v1，vn）路径，如果D 中有一条（v1，vn）路，P2 满足以下条件：
（1）P2≠P1；
（2）D 中不存在异于P1 的路P，使得W（P1）≤W（P）<W（P2）
则称P2 为D 的第二最短路径。
第三最短路径的定义为：设P2 是D 中第二最短（v1，vn）路径，如果D 中有一条（v1，vn）路P3 满足以下条件：
（1）P3≠P2 并且P3≠P1；
（2）D 中不存在异于P1，P2 的路P，使得W（P2）≤W（P）<W（P3）
则称P3 为D 中第三最短路径。
现给定一有n 个节点的网络，n<=30，求给定两点间的第一、第二和第三最短路径。
【输入】
输入文件route.in 格式如下：
n S T Max （每格数值之间用空格分隔）
M11 M12 … M1n
M21 M22 … M2n
… …
Mn1 Mn2 … Mnn
其中n 为节点数，S 为起点，T 为终点，Max 为一代表无穷大的整数，Mij 描述I 到J 的距离，若Mij=Max，则表示从I 到J 无直接通路，Mii=0。
【输出】
输出文件route.out 包含三条路径的长度（从小到大）。占一行，中间用一个空格分隔
【样例输入】
5 1 5 10000
0 1 3 10000 7
10000 0 1 10000 10000
10000 10000 0 1 4
10000 10000 10000 0 1
10000 1 10000 10000 0
【样例输出】
4 5 6

作者: admin 时间: 2018-4-16 11:51
忘记在哪里看到这个题的了，次短路径经典题目。

首先求出第一短路径；
枚举删除第一短路径上一条边，再求此时的最短路径；总这些较优路径中选一条最短的，即为第2短路径；
求第3短路径方法类似，枚举从第一短路径上删除一条边，第2短路径上删除一条边，再求最短路经；从这些路径中选出最短的即为第3短。
时间复杂度为O(n^4)。

作者: WWX 时间: 2018-4-18 13:15
这到题可以用求第k短路的方法去做
虽然有点小题大作，不过复杂度应该比其它解法要低

作者: WWX 时间: 2018-4-18 13:15
第k短路模板
# include<iostream>
# include<cstdio>
# include<cmath>
# include<algorithm>
# include<cstring>
# include<queue>
using namespace std;
const int mn = 35;
const int inf = 0xfffffff;
struct edge{int to,dis,next;};
edge e1[mn*mn],e2[mn*mn];
int head1[mn],head2[mn],edge_max;
void add(int x,int y,int z)
{
++edge_max;
e1[edge_max].to=y;
e1[edge_max].next=head1[x];
e1[edge_max].dis=z;
head1[x]=edge_max;
e2[edge_max].to=x;
e2[edge_max].dis=z;
e2[edge_max].next=head2[y];
head2[y]=edge_max;
}
struct node{
int id,f,g;
node(int id=0,int f=0,int g=0):id(id),f(f),g(g){}
bool operator <(const node &a)const{
      if(f==a.f) return g>a.g;
      return f>a.f;
}
};
int dis[mn];
bool vis[mn];
int n,st,en,maxn,k;
void spfa(int x)
{
queue<int> q;
for(int i=1;i<=n;i++)
      dis[i]=inf;
dis[x]=0;
vis[x]=1;
q.push(x);
while(!q.empty())
{
      int u=q.front();
      q.pop();
      vis[u]=0;
      for(int i=head2[u];i;i=e2[i].next)
      {
         if(dis[e2[i].to]>dis[u]+e2[i].dis)
         {
            dis[e2[i].to]=dis[u]+e2[i].dis;
            if(!vis[e2[i].to])
            {
                  vis[e2[i].to]=1;
                  q.push(e2[i].to);
            }
         }
      }
}
}
void A_star(int x,int y){
if(x==y) k++;
priority_queue<node>q;
q.push(node(x,0,0));
int cnt=0;
while(!q.empty()){
      node h=q.top();q.pop();
      if(h.id==y){
         if(++cnt==k){
            printf("%d ",h.f);
            return ;
         }
      }
      for(int i=head1[h.id];i;i=e1[i].next){
         q.push(node(e1[i].to,h.g+e1[i].dis+dis[e1[i].to],h.g+e1[i].dis));
      }
}
}
int main()
{
int x;
freopen("route.in","r",stdin);
freopen("route.out","w",stdout);
scanf("%d%d%d%d",&n,&st,&en,&maxn);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
   scanf("%d",&x);
   if(x==maxn || i==j)
      continue;
   add(i,j,x);
}
spfa(en);
for(k=1;k<=3;k++)
   A_star(st,en);
return 0;
}

作者: WWX 时间: 2018-4-18 13:26
带注释的代码
# include<iostream>
# include<cstdio>
# include<cmath>
# include<algorithm>
# include<cstring>
# include<queue>
using namespace std;
const int mn = 35;
const int inf = 0xfffffff;
struct edge{int to,dis,next;};
edge e1[mn*mn],e2[mn*mn];//e1存正向边，e2存反向边
int head1[mn],head2[mn],edge_max;
void add(int x,int y,int z)//加边
{
++edge_max;
e1[edge_max].to=y;
e1[edge_max].next=head1[x];
e1[edge_max].dis=z;
head1[x]=edge_max;
e2[edge_max].to=x;
e2[edge_max].dis=z;
e2[edge_max].next=head2[y];
head2[y]=edge_max;
}
struct node{
int id,f,g;//id为节点编号，g为估计函数
node(int id=0,int f=0,int g=0):id(id),f(f),g(g){}
bool operator <(const node &a)const{
      if(f==a.f) return g>a.g;
      return f>a.f;
}
};
int dis[mn];
bool vis[mn];
int n,st,en,maxn,k;
void spfa(int x)//预处理终点到各个节点到的最短路
{
queue<int> q;
for(int i=1;i<=n;i++)
      dis[i]=inf;
dis[x]=0;
vis[x]=1;
q.push(x);
while(!q.empty())
{
      int u=q.front();
      q.pop();
      vis[u]=0;
      for(int i=head2[u];i;i=e2[i].next)
      {
         if(dis[e2[i].to]>dis[u]+e2[i].dis)
         {
            dis[e2[i].to]=dis[u]+e2[i].dis;
            if(!vis[e2[i].to])
            {
                  vis[e2[i].to]=1;
                  q.push(e2[i].to);
            }
         }
      }
}
}
void A_star(int x,int y){//第k短路模板
priority_queue<node>q;
q.push(node(x,0,0));
int cnt=0;
while(!q.empty()){
      node h=q.top();q.pop();
      if(h.id==y){
         if(++cnt==k){//如果是第k次找到这个点，那么第k短路就是h.f
            printf("%d ",h.f);
            return ;
         }
      }
      for(int i=head1[h.id];i;i=e1[i].next){
         q.push(node(e1[i].to,h.g+e1[i].dis+dis[e1[i].to],h.g+e1[i].dis));
      }
}
}
int main()
{
int x;
freopen("route.in","r",stdin);
freopen("route.out","w",stdout);
scanf("%d%d%d%d",&n,&st,&en,&maxn);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
   scanf("%d",&x);
   if(x==maxn || i==j)
      continue;
   add(i,j,x);//加边
}
spfa(en);//预处理,不要忘了。（血的教训）
for(k=1;k<=3;k++)
   A_star(st,en);
return 0;
}

欢迎光临华师一附中OI组 (http://hsyit.cn/)