SDUT 2498-AOE网上的关键路径(spfa+字典序路径) - c++编程基础

TOP

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

2015-07-20 17:39:17 来源: 作者: 【大中小】浏览:3次

AOE网上的关键路径

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

题目描述

一个无环的有向图称为无环图（Directed Acyclic Graph），简称DAG图。
AOE(Activity On Edge)网：顾名思义，用边表示活动的网，当然它也是DAG。与AOV不同，活动都表示在了边上，如下图所示：

如上所示，共有11项活动（11条边），9个事件（9个顶点）。整个工程只有一个开始点和一个完成点。即只有一个入度为零的点（源点）和只有一个出度为零的点（汇点）。
关键路径：是从开始点到完成点的最长路径的长度。路径的长度是边上活动耗费的时间。如上图所示，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)。数据保证图连通。

输出

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

示例输入

示例输出

最长路+记录字典序最小路径（即如果有多条最长路输出字典序最小的那条 比如 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 long const 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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 1679 The Unique MST，次小生..	下一篇：hdu 4056 Draw a Mess(数据结构-..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: