首页 晴问-关键路径长度 & 关键活动 & 关键路径
文章
取消

晴问-关键路径长度 & 关键活动 & 关键路径

发表于 2022/08/21 更新于 2022/08/23
作者 ,
10 分钟阅读

关键路径长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 110;
struct node
{
    int v, w;
    node(int _v, int _w) : v(_v), w(_w) {}
};
int n, m;
vector<vector<node>> neighbor(maxn);
vector<int> inDegree(maxn, 0);
int ve[maxn];
int vl[maxn];
stack<int> reverseTopo;
int criticalLen = 0;
bool TopoLogicalSort()
{
    memset(ve, 0, sizeof(ve));
    queue<int> q;
    for (int i = 0; i < n; i++)
    {
        if (inDegree[i] == 0)
        {
            q.push(i);
            reverseTopo.push(i);
        }
    }
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (node n : neighbor[u])
        {
            int v = n.v, w = n.w;
            //更新入度，判断是否进队
            inDegree[v]--;
            if (inDegree[v] == 0)
            {
                q.push(v);
                reverseTopo.push(v);
            }
            //更新最早开始时间 数组
            if (ve[u] + w > ve[v])
            {
                ve[v] = ve[u] + w;
            }
        }
    }
    if (reverseTopo.size() == n) return true;
    else return false;
}
int CriticalPath()
{
    int maxW = 0;
    for (int i = 0; i < n; i++)
    {
        if (ve[i] > maxW) maxW = ve[i];
    }
    return maxW;
    /*
    fill(vl, vl + n, maxW);
    while (!reverseTopo.empty())
    {
        int u = reverseTopo.top();
        reverseTopo.pop();
        for (node n : neighbor[u])
        {
            int v = n.v, w = n.w;
            if (vl[v] - w < vl[u])
            {
                vl[u] = vl[v] - w;
            }
        }
    }
    //计算每个关键路径的权值，不一定是关键路径（一条）的长度，可能有分支
    for (int u = 0; u < n; u++)
    {
        for (node n : neighbor[u])
        {
            int v = n.v, w = n.w;
            int e = ve[u], l = vl[v] - w;
            if (e == l)
            {
                criticalLen += w;
            }

        }
    }
    */
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;
        inDegree[v2]++;
        neighbor[v1].emplace_back(node(v2, w));
    }

    if (TopoLogicalSort()) cout << "Yes" << endl<< CriticalPath();
    else
    {
        cout << "No";
        return 0;
    }
}

    起初我是把vl数组也算出来了，但实际上没必要，反而会出错。因为算vl数组去判断每条边的e与v是否相等，是用来判断这个边是否为关键路径的一条边，但题目问的是关键路径长度，也就是说，是一条路径的最大长度，直接返回汇点或者说是最后一个节点的ve即可。

关键活动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 110;
struct node
{
    int v, w;
    node(int _v, int _w) : v(_v), w(_w) {}
};
struct criticalEdge
{
    int u, v, w;
    criticalEdge(int _u, int _v, int _w) :u(_u), v(_v), w(_w) {}
};
int n, m;
vector<vector<node>> neighbor(maxn);
vector<criticalEdge> path;
vector<int> inDegree(maxn, 0);
int ve[maxn];
int vl[maxn];
stack<int> reverseTopo;
int criticalLen = 0;
bool TopoLogicalSort()
{
    memset(ve, 0, sizeof(ve));
    queue<int> q;
    for (int i = 0; i < n; i++)
    {
        if (inDegree[i] == 0)
        {
            q.push(i);
            reverseTopo.push(i);
        }
    }
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (node n : neighbor[u])
        {
            int v = n.v, w = n.w;
            //更新入度，判断是否进队
            inDegree[v]--;
            if (inDegree[v] == 0)
            {
                q.push(v);
                reverseTopo.push(v);
            }
            //更新最早开始时间 数组
            if (ve[u] + w > ve[v])
            {
                ve[v] = ve[u] + w;
            }
        }
    }
    if (reverseTopo.size() == n) return true;
    else return false;
}
void CriticalPath()
{
    int maxW = 0;
    for (int i = 0; i < n; i++)
    {
        if (ve[i] > maxW) maxW = ve[i];
    }
    fill(vl, vl + n, maxW);
    while (!reverseTopo.empty())
    {
        int u = reverseTopo.top();
        reverseTopo.pop();
        for (node n : neighbor[u])
        {
            int v = n.v, w = n.w;
            if (vl[v] - w < vl[u])
            {
                vl[u] = vl[v] - w;
            }
        }
    }
    //计算每个关键路径的权值，不一定是关键路径（一条）的长度，可能有分支
    for (int u = 0; u < n; u++)
    {
        for (node n : neighbor[u])
        {
            int v = n.v, w = n.w;
            int e = ve[u], l = vl[v] - w;
            if (e == l)
            {
                path.emplace_back(criticalEdge(u,v,w));
            }

        }
    }
}
bool comp(criticalEdge& e1 , criticalEdge& e2)
{
    if (e1.u != e2.u)
        return e1.u < e2.u;
    else return e1.v < e2.v;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;
        inDegree[v2]++;
        neighbor[v1].emplace_back(node(v2, w));
    }

    if (TopoLogicalSort())
    {
        CriticalPath();
        cout << "Yes" << endl;
        sort(path.begin(), path.end(), comp);
        for (criticalEdge e: path)
        {
            cout << e.u << ' ' << e.v << endl;
        }
    }
    else
    {
        cout << "No";
    }
}

    其实跟上面的代码差不多，就是这个存路径，其实不一定非得开个结构体，pair也是可以的，那么为什么我开了一个结构体呢，因为一开始我还以为要输出边权。需要注意的就是关键路径函数要在拓扑排序函数执行后再运行。

关键路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<cstring>
#include<set>
using namespace std;

const int maxn = 110;
struct node
{
    int v, w;
    node(int _v, int _w) : v(_v), w(_w) {}
};

int n, m;
vector<vector<node>> neighbor(maxn);
vector<set<int>> criticalNeighbor(maxn);
vector<int> inDegree(maxn, 0), inDegreeOrigin(maxn, 0);
int ve[maxn];
int vl[maxn];
stack<int> reverseTopo;
int criticalLen = 0;
bool TopoLogicalSort()
{
    memset(ve, 0, sizeof(ve));
    queue<int> q;
    for (int i = 0; i < n; i++)
    {
        if (inDegree[i] == 0)
        {
            q.push(i);
            reverseTopo.push(i);
        }
    }
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (node n : neighbor[u])
        {
            int v = n.v, w = n.w;
            //更新入度，判断是否进队
            inDegree[v]--;
            if (inDegree[v] == 0)
            {
                q.push(v);
                reverseTopo.push(v);
            }
            //更新最早开始时间 数组
            if (ve[u] + w > ve[v])
            {
                ve[v] = ve[u] + w;
            }
        }
    }
    if (reverseTopo.size() == n) return true;
    else return false;
}
void CriticalPath()
{
    int maxW = 0;
    for (int i = 0; i < n; i++)
    {
        if (ve[i] > maxW) maxW = ve[i];
    }
    fill(vl, vl + n, maxW);
    while (!reverseTopo.empty())
    {
        int u = reverseTopo.top();
        reverseTopo.pop();
        for (node n : neighbor[u])
        {
            int v = n.v, w = n.w;
            if (vl[v] - w < vl[u])
            {
                vl[u] = vl[v] - w;
            }
        }
    }
    //计算每个关键路径的权值，不一定是关键路径（一条）的长度，可能有分支
    for (int u = 0; u < n; u++)
    {
        for (node n : neighbor[u])
        {
            int v = n.v, w = n.w;
            int e = ve[u], l = vl[v] - w;
            if (e == l)
            {
                criticalNeighbor[u].insert(v);
            }

        }
    }
}
vector<int> path;
void dfs(int u)
{
    if (criticalNeighbor[u].size() == 0)
    {
        for (int i = 0; i < path.size(); i++)
        {
            if (i != 0) cout << "->";
            cout << path[i];
        }
        cout << endl;
    }

    for (int v : criticalNeighbor[u])
    {
        path.emplace_back(v);
        dfs(v);
        path.pop_back();
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;
        inDegree[v2]++;
        inDegreeOrigin[v2]++;
        neighbor[v1].emplace_back(node(v2, w));
    }

    if (TopoLogicalSort())
    {
        CriticalPath();
        cout << "Yes" << endl;
        for (int i = 0; i < n; i++)
        {
            if (inDegreeOrigin[i] == 0)
            {
                path.emplace_back(i);
                dfs(i);
                path.pop_back();
            }
        }
    }
    else
    {
        cout << "No";
    }
}

    经典使用vector数组和dfs来存储每一条路。

算法刷题
关键路径
本文由作者按照 CC BY 4.0 进行授权
最近更新
文章内容