SDUT 2498-AOE网上的关键路径(spfa+字典序路径)-白红宇

SDUT 2498-AOE网上的关键路径(spfa+字典序路径)

阅读量：5935 次

发布时间：2019-06-19

本文共 2649 字，大约阅读时间需要 8 分钟。

AOE网上的关键路径

Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^

题目描写叙述

一个无环的有向图称为无环图（Directed Acyclic Graph），简称DAG图。

AOE(Activity On Edge)网：顾名思义，用边表示活动的网，当然它也是DAG。与AOV不同，活动都表示在了边上，例如以下图所看到的：

如上所看到的，共同拥有11项活动（11条边），9个事件（9个顶点）。整个project仅仅有一个開始点和一个完毕点。即仅仅有一个入度为零的点（源点）和仅仅有一个出度为零的点（汇点）。

关键路径：是从開始点到完毕点的最长路径的长度。路径的长度是边上活动耗费的时间。如上图所看到的，1 到2 到 5到7到9是关键路径（关键路径不止一条，请输出字典序最小的），权值的和为18。

输入

这里有多组数据，保证不超过10组，保证仅仅有一个源点和汇点。输入一个顶点数n(2<=n<=10000),边数m(1<=m <=50000),接下来m行，输入起点sv，终点ev,权值w（1<=sv,ev<=n,sv != ev,1<=w <=20)。数据保证图连通。

输出

关键路径的权值和，而且从源点输出关键路径上的路径（假设有多条，请输出字典序最小的）。

演示样例输入

9 111 2 61 3 41 4 52 5 13 5 14 6 25 7 95 8 76 8 48 9 47 9 2

演示样例输出

181 22 55 77 9

最长路+记录字典序最小路径（即假设有多条最长路输出字典序最小的那条 比方 1->2->4 和 1->3->4 都符合最长路，那么输出1->2->4 ） 主要实现就是在松弛时，当dis[v]==dis[u]+w 时，推断一下路径的字典序来决定是否更新路径，眼下还是仅仅会暴力推断QAQ

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  using namespace std;#define LL long longconst int INF = 0x3f3f3f3f;int s1[10010], s2[10010], ans[10010], dis[10010], in[10010], out[10010], path[10010], n, m, s, e;bool vis[10010];vector 
                  
                   
                     > eg[50010];bool ok(int u, int v){ int p = v, num1 = 0; s1[num1++] = v; while (path[p] != -1) { s1[num1++] = path[p]; p = path[p]; } p = u; int num2 = 0; s2[num2++] = v; s2[num2++] = u; while (path[p] != -1) { s2[num2++] = path[p]; p = path[p]; } int i = num1 - 1, j = num2 - 1; while (i >= 0 && j >= 0) { if (s1[i] > s2[j]) { return 1; } i--; j--; } return 0;}void spfa(){ queue 
                    
                      Q; for (int i = 1; i <= n; i++) { dis[i] = -INF; } dis[s] = 0; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); vis[u] = 0; for (int i = 0; i < eg[u].size(); i++) { int v = eg[u][i].first; int w = eg[u][i].second; if (dis[v] < dis[u] + w) { dis[v] = dis[u] + w; path[v] = u; if (!vis[v]) { vis[v] = 1; Q.push(v); } } else if (dis[v] == dis[u] + w && ok(u, v)) { path[v] = u ; if (!vis[v]) { vis[v] = 1; Q.push(v); } } } }}void print(){ int p = e, num = 0; while (path[p] != -1) { ans[num++] = path[p]; p = path[p]; } printf("%d\n", dis[e]); for (int i = num - 1; i > 0; i--) { printf("%d %d\n", ans[i], ans[i - 1]); } printf("%d %d\n", ans[0], e);}int main(){ int u, v, c; while (~scanf("%d %d", &n, &m)) { for (int i = 0; i <= n; i++) { eg[i].clear(); } memset(in, 0, sizeof(in)); memset(out, 0, sizeof(out)); memset(vis, 0, sizeof(vis)); memset(path, -1, sizeof(path)); while (m--) { scanf("%d%d%d", &u, &v, &c); eg[u].push_back(make_pair(v, c)); in[v]++; out[u]++; } for (int i = 1; i <= n; i++) { if (!in[i]) { s = i; } if (!out[i]) { e = i; } } spfa(); print(); } return 0;}

转载地址：http://kdjtx.baihongyu.com/

你可能感兴趣的文章