xfstart07
Get busy living or get busy dying

第一二个问是标准的最短路经没什么好说,直接用Dijkstra或SPFA即可。只要是第三个问,求次短路。

简单的求次短路方法和求次小生成树基本一样,也是枚举删除一条最短路上的边,在求最短路,再从求出

的值中找出最小的即可。


次短路还有一些扩展可以查看byvoid大牛的blog。


  1 /*
  2  * Problem: HAOI 2005 路由选择问题
  3  * Author: Xu Fei
  4  * Time: 2010.8.2 13.59
  5  * Method: Dijkstra  次短路
  6  */
  7  
  8 #include<iostream>
  9 #include<cstdio>
 10 #include<cstring>
 11 using namespace std;
 12 
 13 const int MaxN=55,INF=0xFFFFFFF;
 14 
 15 struct Node{
 16     int x,y;
 17 }Path[MaxN];
 18 
 19 int N,S,T,Lp,Len;
 20 int S0,S1,S2;
 21 int P[MaxN];
 22 int dis[MaxN];
 23 bool vis[MaxN];
 24 int pre[MaxN];
 25 int temp[MaxN][MaxN];
 26 int cost[MaxN][MaxN];
 27 
 28 void into()
 29 {
 30     int i,j;
 31     
 32     scanf("%d%d%d",&N,&S,&T);
 33     for(i=1;i<=N;++i)
 34     {
 35         for(j=1;j<=N;++j)
 36         {
 37             scanf("%d",&cost[i][j]);
 38             if(cost[i][j]==0)
 39                 cost[i][j]=INF;
 40         }
 41     }
 42     scanf("%d",&Lp);
 43     for(i=1;i<=Lp;++i)
 44         scanf("%d",P+i);
 45 }
 46 void change(bool flag)
 47 {
 48     int i,j;
 49     
 50     if(flag)
 51     {
 52         memcpy(temp,cost,sizeof(cost));
 53         for(i=1;i<=Lp;++i)
 54             for(j=1;j<=N;++j)
 55                 cost[P[i]][j]=INF;
 56     }
 57     else
 58     {
 59         memcpy(cost,temp,sizeof(cost));
 60     }
 61 }
 62 int dijkstra()
 63 {
 64     int i,j,Min,kj;
 65     
 66     for(i=1;i<=N;++i)
 67     {
 68         dis[i]=cost[S][i];
 69         vis[i]=true;
 70         pre[i]=S;
 71     }
 72     dis[S]=0;
 73     vis[S]=false;
 74     for(i=1;i<N;++i)
 75     {
 76         Min=INF;
 77         for(j=1;j<=N;++j)
 78             if(vis[j]&&dis[j]<Min)
 79                 Min=dis[j],kj=j;
 80         if(kj==T) break;
 81         vis[kj]=false;
 82         for(j=1;j<=N;++j)
 83             if(vis[j]&&dis[j]>dis[kj]+cost[kj][j])
 84             {
 85                 dis[j]=dis[kj]+cost[kj][j];
 86                 pre[j]=kj;
 87             }
 88     }
 89     return dis[T];
 90 }
 91 void solve()
 92 {
 93     int i,tmp,Min;
 94     
 95     change(true);
 96     S0=dijkstra();
 97     change(false);
 98     S1=dijkstra();
 99     Len=0;
100     i=T;
101     while(i!=S)
102     {
103         Len++;
104         Path[Len].x=pre[i];
105         Path[Len].y=i;
106         i=pre[i];
107     }
108     S2=INF;
109     for(i=1;i<=Len;++i)
110     {
111         tmp=cost[Path[i].x][Path[i].y];
112         cost[Path[i].x][Path[i].y]=INF;
113         cost[Path[i].y][Path[i].x]=INF;
114         Min=dijkstra();
115         cost[Path[i].x][Path[i].y]=tmp;
116         cost[Path[i].y][Path[i].x]=tmp;
117         if(S2>Min)
118             S2=Min;
119     }
120     printf("%d %d %d\n",S0,S1,S2);
121 }
122 int main()
123 {
124     freopen("t.in","r",stdin);
125     freopen("t.out","w",stdout);
126     
127     into();
128     solve();
129     return 0;
130 }

 


路由选择问题(T1)

【问题描述】

    X城有一个含有N个节点的通信网络,在通信中,我们往往关心信息从一个节点I传输到节点J的最短路径。遗憾的是,由于种种原因,线路中总有一些节点会出故障,因此在传输中要避开故障节点。
任务一:在己知故障节点的情况下,求避开这些故障节点,从节点I到节点J的最短路径S0。
任务二:在不考虑故障节点的情况下,求从节点I到节点J的最短路径S1、第二最短路径S2。

【输入文件】

第1行: N I J (节点个数 起始节点 目标节点)
第2—N+1行: Sk1 Sk2…SkN (节点K到节点J的距离为SkJ K=1,2,……,N)
最后一行: P T1 T2……Tp (故障节点的个数及编号)

【输出文件】

S0 S1 S2 (S1<=S2 从节点I到节点J至少有两条不同路径)

t1.in

5 1 5
0 10 5 0 0
10 0 0 6 20
5 0 0 30 35
0 6 30 0 6
0 20 35 6 0
1 2

t2.out

40 22 30

【约束条件】

(1)N<=50 N个节点的编号为1,2,…,N
(2)Skj为整数,Skj<=100,(K,J=1,2…,N 若Skj=0表示节点K到节点J没线路)
(3)P<=5


posted on 2010-08-02 14:02 xfstart07 阅读(186) 评论(0)  编辑 收藏 引用 所属分类: 竞赛题库图论

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理