ZOJ3088

题意:给定同一个图上的两种路径,求出从某点出发到另一点的路径长度来回长度之比最大的情况,最后还要输出路径。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 #include <queue>
  7 using namespace std;
  8 #define inf 9999999
  9 #define N 1005
 10 #define M 1005
 11 struct Edge
 12 {
 13     int v,w,next;
 14     Edge(){}
 15     Edge(int V,int W,int NEXT):v(V),w(W),next(NEXT){}
 16 }edge1[M],edge2[M];
 17 int path1[N][N],path2[N][N];
 18 // path1存下坡从i到j的最长路的路径,path2存上坡从i到j的最短路的路径 
 19 int dis1[N][N],dis2[N][N];
 20 // dis1存下坡从i到j的最长路,dis2存上坡从i到j的最短路
 21 int head1[N],head2[N];
 22 int n,m,k,size1,size2,vis[N];
 23 
 24 void Init() // 初始化 
 25 {
 26     size1 = 0;
 27     size2 = 0;
 28     memset(head1,-1,sizeof(head1));
 29     memset(head2,-1,sizeof(head2));
 30 }
 31 void InsertEdge1(int u,int v,int w) //加下坡的边 
 32 {
 33     edge1[size1] = Edge(v,w,head1[u]);
 34     head1[u] = size1++;
 35 }
 36 void InsertEdge2(int u,int v,int w) //加上坡的边 
 37 {
 38     edge2[size2] = Edge(v,w,head2[u]);
 39     head2[u] = size2++;
 40 }
 41 
 42 void spfa1(int st,int* head,int* path,int* dis,Edge* edge) //求下坡的最长路 
 43 {
 44     for(int i=1; i<=n; i++)
 45     {
 46         vis[i] = 0;
 47         dis[i] = -1; // 
 48         path[i] = -1;
 49     }
 50     vis[st] = 1; dis[st] = 0;
 51     queue<int> Q;
 52     Q.push(st);
 53     while(!Q.empty())
 54     {
 55         int u = Q.front();
 56         Q.pop();
 57         vis[u] = 0;
 58         for(int i=head[u]; i!=-1; i=edge[i].next)
 59         {
 60             int v = edge[i].v;
 61             if(dis[v] < dis[u] + edge[i].w) // 
 62             {
 63                 dis[v] = dis[u] + edge[i].w ;
 64                 path[v] = u;
 65                 if(!vis[v])
 66                 {
 67                     vis[v] = 1;
 68                     Q.push(v);
 69                 }
 70             }
 71         }
 72     }
 73 }
 74 
 75 void spfa2(int st,int* head,int* path,int* dis,Edge* edge) //求上坡最短路 
 76 {
 77     for(int i=1; i<=n; i++)
 78     {
 79         vis[i] = 0;
 80         dis[i] = inf; //
 81         path[i] = -1;
 82     }
 83     vis[st] = 1; dis[st] = 0;
 84     queue<int> Q;
 85     Q.push(st);
 86     while(!Q.empty())
 87     {
 88         int u = Q.front();
 89         Q.pop();
 90         vis[u] = 0;
 91         for(int i=head[u]; i!=-1; i=edge[i].next)
 92         {
 93             int v = edge[i].v;
 94             if(dis[v] > dis[u] + edge[i].w) //
 95             {
 96                 dis[v] = dis[u] + edge[i].w;
 97                 path[v] = u;
 98                 if(!vis[v])
 99                 {
100                     vis[v] = 1;
101                     Q.push(v);
102                 }
103             }
104         }
105     }
106 }
107 
108 int main()
109 {
110     int T;
111     scanf("%d",&T);
112     while(T--)
113     {
114         scanf("%d%d%d",&n,&m,&k);
115         Init();
116         int u,v,w;
117         for(int i=0; i<m; i++)
118         {
119             scanf("%d%d%d",&u,&v,&w);
120             InsertEdge1(u,v,w);
121         }
122         for(int i=0; i<k; i++)
123         {
124             scanf("%d%d%d",&u,&v,&w);
125             InsertEdge2(u,v,w);
126         }
127         for(int i=1; i<=n; i++)
128         {
129             spfa1(i,head1,path1[i],dis1[i],edge1); // 对每个点求下坡最长路 
130             spfa2(i,head2,path2[i],dis2[i],edge2); // 对每个点求上坡最短路 
131         }
132         double ans = 0;
133         int st,ed;
134         for(int i=1; i<=n; i++) //枚举 
135         for(int j=1; j<=n; j++)
136         {
137             if(i!=j && dis1[i][j]!=-1 && dis2[j][i] != inf)
138             {
139                 double Rate = (1.0*dis1[i][j])/(1.0*dis2[j][i]);
140                 if(Rate > ans)
141                 {
142                     st = i; //记录起点 
143                     ed = j; //记录终点 
144                     ans = Rate; //最后输出的值 
145                 }
146             }
147         }
148         int a1[N],a2[N];
149         int k1 = 0 , k2 = 0;
150         int S=st,E=ed,d;
151         d = S;
152         while(d!=-1) // 上坡的路径 
153         {
154             a2[k2++] = d;
155             d = path2[E][d];
156         }
157         for(int i=k2-1; i>=0; i--)
158         printf("%d ",a2[i]);
159         d = E;
160         while(d!=-1) //下坡的路径 
161         {
162             a1[k1++] = d;
163             d = path1[S][d];
164         }
165         for(int i=k1-2; i>0; i--)
166         printf("%d ",a1[i]);
167         printf("%d
",a1[0]);
168         printf("%.3f
",ans);
169     }
170     return 0;
171 }
View Code
原文地址:https://www.cnblogs.com/ar940507/p/3245692.html