c++给定有向无环网的顶点数、弧数、弧的信息，输出各关键路径上活动信息。X组测试数据，对于每组测试数据， 第一行输入顶点数N（N<=100），弧数M，数据之间空格分隔； 第二行输入M条弧的信息（v1 v2 dut表示弧尾、弧头及权值），数据之间由空格分隔；X组测试数据，对于每组测试数据， 第一行输入顶点数N（N<=100），弧数M，数据之间空格分隔； 第二行输入M条弧的信息（v1 v2 dut表示弧尾、弧头及权值），数据之间由空格分隔；

好的，这是一个典型的关键路径问题，需要用到拓扑排序和动态规划的思想来解决。

首先，我们需要根据给定的弧的信息构建有向无环图，并计算每个顶点的入度。然后，我们进行拓扑排序，得到每个顶点的拓扑序号，同时记录每个顶点的最早开始时间和最晚开始时间。接着，我们需要进行动态规划，根据最早开始时间和最晚开始时间计算每个活动的最早开始时间和最晚开始时间，以及每个活动的关键路径。

下面是完整的 C++ 代码实现：

相关问题

c++给定有向无环图的顶点数、弧数、弧的信息，输出该图的拓扑排序的顶点序列。X组测试数据，对于每组测试数据， 第一行输入顶点数N（N<=100），弧数M，数据之间空格分隔； 第二行输入M条弧的信息（v1 v2表示弧尾、弧头），数据之间由空格分隔；按格式输出该图的拓扑排序的顶点序列，顶点信息之间由空格分隔。

好的，这是一个经典的拓扑排序问题，可以使用 Kahn算法来解决。

Kahn算法的基本思想是：首先找到一个入度为0的点，将其输出并从图中删除，然后更新与该点相邻的点的入度，重复执行这个过程直到图为空或者不存在入度为0的点为止。

以下是C++的代码实现：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 105;

int n, m;
int indegree[MAXN];
vector<int> G[MAXN];

void topsort() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];
            indegree[v]--;
            if (indegree[v] == 0) {
                q.push(v);
            }
        }
    }
}

int main() {
    while (cin >> n >> m) {
        for (int i = 1; i <= n; i++) {
            G[i].clear();
            indegree[i] = 0;
        }
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            G[u].push_back(v);
            indegree[v]++;
        }
        topsort();
        cout << endl;
    }
    return 0;
}

输入格式如下：

5 6
1 2 1 3 2 3 2 4 3 5 4 5

输出格式如下：

1 2 3 4 5

希望能帮到你！

c++给定有向网的顶点数、弧数、弧的信息，输出由给定源点出发到各个顶点的最短路径长度。X组测试数据，对于每组测试数据， 第一行输入顶点数N（N<=100），弧数M，给定源点，数据之间空格分隔； 第二行输入M条弧的信息（v1 v2 dut表示弧尾、弧头及权值），数据之间由空格分隔。按格式输出由给定源点出发到各个顶点的最短路径的长度。

这是一个经典的单源最短路径问题，可以使用Dijkstra算法或者Bellman-Ford算法解决。下面是使用Dijkstra算法的C++代码实现：

#include <iostream>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;

int n, m, s; //顶点数，弧数，源点
int dis[105]; //源点到各个顶点的最短路径长度
bool vis[105]; //标记顶点是否已被访问
int g[105][105]; //邻接矩阵存储图

void Dijkstra()
{
    memset(vis, false, sizeof(vis));
    memset(dis, INF, sizeof(dis));
    dis[s] = 0;
    for(int i = 1; i <= n; i++)
    {
        int u = -1, minn = INF;
        for(int j = 1; j <= n; j++)
        {
            if(!vis[j] && dis[j] < minn)
            {
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) return; //图不连通
        vis[u] = true;
        for(int v = 1; v <= n; v++)
        {
            if(!vis[v] && g[u][v] != INF && dis[u] + g[u][v] < dis[v])
            {
                dis[v] = dis[u] + g[u][v];
            }
        }
    }
}

int main()
{
    while(cin >> n >> m >> s)
    {
        memset(g, INF, sizeof(g));
        for(int i = 1; i <= m; i++)
        {
            int u, v, w;
            cin >> u >> v >> w;
            g[u][v] = w;
        }
        Dijkstra();
        for(int i = 1; i <= n; i++)
        {
            if(dis[i] == INF) cout << "INF" << endl;
            else cout << dis[i] << endl;
        }
    }
    return 0;
}

输入格式：

5 7 1
1 2 2
1 3 3
2 4 1
2 5 4
3 4 2
4 5 3
5 3 5

输出格式：

0
2
3
5
8