关键路径算法问题，答案错误50分

Question

关键路径、拓扑排序题目。
传送门

样例

样例输入

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

样例输出

7
1 2 3 5

代码50分。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int NN=105;
struct node{
    int y,w;
};
int n,m,rd[NN],day[NN],pre[NN];
vector<node>e[105]; 
void tuopu()
{
    queue<int>q;
    for(int i=1;i<=n;i++)
    {
        if(rd[i]==0)
        {
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(auto ha:e[x])
        {
            int y=ha.y,w=ha.w;
            if(day[x]+w>day[y])
            {
                pre[y]=x;
                day[y]=day[x]+w;
            }
            rd[y]--;
            if(rd[y]==0)
            {
                q.push(y);
            }
        }
    }
}
void dfs(int oo)
{
    if(pre[oo]!=0) dfs(pre[oo]);
    printf("%d ",oo);
}
int main()
{
    scanf("%d%d",&n,&m);
    n++; 
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        e[x].push_back(node{y,z});
        rd[y]++;
    }
    tuopu();
    int anss=0;
    for(int i=1;i<=n;i++) anss=max(anss,day[i]);
    printf("%d\n",anss);
    dfs(n);
}

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 你可以看下这个问题的回答https://ask.csdn.net/questions/7441669
• 你也可以参考下这篇文章：回文数猜测：所谓回文数，即顺序与逆序均为相同的整数。如292、10301均为回文数。
• 除此之外, 这篇博客: 克鲁斯卡尔算法中的 将图中边按照权值从小到大排列，然后从最小的边开始扫描，设置一个边的集合来记录，如果该边并入不构成回路的话，则将该边并入当前生成树。直到所有的边都检测完为止。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
  

  
  
  

  #include<iostream>
  #include<stdio.h>
  #include<stdlib.h>
  using namespace std;
  #define MaxSize 100   // 顶点数目的最大值
  typedef char VertexType;  // 顶点的数据类型
  typedef int EdgeType;  // 整数表示权值
  
  typedef struct{
  	int a;  // 较小值的顶点
  	int b;  // 边的两个顶点
  	int weight;  // 边的权值
  }Edge;  // 边结构体
  
  typedef struct{
  	VertexType Vex[MaxSize];  // 顶点表
  	EdgeType Edge[MaxSize][MaxSize];  // 邻接矩阵
  	int vexnum, arcnum;  // 图的当前节点数和弧数
  }MGraph;
  
  Edge edges[MaxSize];
  void CreateGraph(MGraph *g){
  	int start;
  	int end;  
  	int weight;
  	cout << "请输入图的边数和顶点数(空格分隔)：";
  	cin >> g->vexnum >> g->arcnum;
  	// 初始化顶点
  	for (int i = 0; i < g->vexnum; ++i){
  		cout << "请输入节点" << i << "的值(字符)：";
  		cin >> g->Vex[i];
  	}
  
  	//初始化邻接矩阵
  	for (int i = 0; i < g->vexnum; ++i){
  		for (int j = 0; j < g->vexnum; ++j){
  			g->Edge[i][j] = 65536;  // 不可达
  		}
  	}
  	
  	for (int i = 0; i < g->arcnum / 2; ++i){
  		printf("请输入第%d段弧(i j)和权值：", i);
  		cin >> end >> start >> weight;
  		g->Edge[end][start] = weight;
  		g->Edge[start][end] = weight;
  		Edge temp;
  		if (start > end){
  			temp.a = end;
  			temp.b = start;
  		}
  		else{			
  			temp.a = start;
  			temp.b = end;
  		}
  		temp.weight = weight;
  		edges[i] = temp;
  	}
  }
  
  // 并查集
  int Find(int *parent, int x){  // 寻找根节点
  	while (parent[x] >= 0)
  		x = parent[x];
  	return x;
  }
  
  // 冒泡排序
  void sort(Edge e[],int len){
  	for (int i = 0; i < len; ++i){
  		for (int j = 0; j < len - 1 - i; ++j){
  			if (e[j].weight > e[j + 1].weight){
  				Edge temp = e[j];
  				e[j] = e[j + 1];
  				e[j + 1] = temp;
  			}
  		}
  	}
  }
  
  int parent[MaxSize];  // Edge edges[MaxSize];  // 边数组父亲顶点数组(并查集)
  
  void MiniSpanTree_Kruskal(MGraph g){
  	int n, m;
  	sort(edges, g.arcnum);
  	for (int i = 0; i < g.vexnum; ++i) parent[i] = -1;  // 初始化：各个顶点单独形成一个集合
  	for (int i = 0; i < g.arcnum; ++i){  // 扫描每一条边
  		n = Find(parent, edges[i].a);
  		m = Find(parent, edges[i].b);  // a-------->b
  		if (n != m){
  			parent[n] = m;  // 并操作,将n并入m中
  			// 作为生成树的一条边打印出来
  			cout << edges[i].a << "->" << edges[i].b<<" ";
  		}
  	}
  }
  
  void main(){
  	MGraph *g = new MGraph;
  	CreateGraph(g);
  	MiniSpanTree_Kruskal(*g);
  	system("pause");
  	return;
  }
  

• 您还可以看一下 孙玖祥老师的图解数据结构与算法课程中的 左旋和右旋的代码实现小节, 巩固相关知识点
  
• 以下回答来自chatgpt:

  我很抱歉，参考资料中并没有与关键路径算法有关的内容。关键路径算法与拓扑排序是密不可分的，可以说是拓扑排序的延伸和应用。拓扑排序是基于有向无环图（DAG）的，关键路径算法就是在DAG上进行的，通过拓扑排序得到DAG的每个定点的入度和出度，然后根据入度和出度求出每个点的最早开始时间和最迟结束时间，从而求出每个关键路径上的关键活动和关键时间。其实你提供的参考资料中的哈希表和查找算法与关键路径算法和拓扑排序并没有太大关系，我这里就不再详细解释了。

  下面是凯撒密码的解答，可以使用字符数组来实现：

  #include <stdio.h>
  #include <string.h>
  
  int main()
  {
      char s[105];
      scanf("%s", s);  // 读入单词
      int len = strlen(s);
      for (int i = 0; i < len; i++) {
          char c = s[i];
          if (c >= 'a' && c <= 'z') {  // 如果是小写字母
              c = c + 3;  // 凯撒加密
              if (c > 'z') {  // 需要循环
                  c = 'a' + c - 'z' - 1;
              }
              s[i] = c;
          }
      }
      printf("%s\n", s);  // 输出密文
      return 0;
  }
  

  代码中的凯撒加密是指将字母表上的每个字母都向后移动3位，如果移动后的字母超过了字母表的最后一个字母z，就需要循环回到字母表的第一个字母a。需要加密的字符串可以通过scanf读入到字符数组中，然后遍历字符数组中的每个字符，如果是小写字母，就对其进行加密，最后输出加密后的字符串即可。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^