题目描述
给定有向图无环的边信息，求每个顶点的最早开始时间、最迟开始时间。
// 参考代码
代码语言：javascript复制#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
class Vertex {
public:
int indexNo;
bool hasEnterQueue;
int early;
int later;
Vertex(int indexNo) {
this->indexNo = indexNo;
this->hasEnterQueue = false;
early = -1;
later = 0x7FFFF;
}
void updateEarly(int parentEarly, int edgeValue) {
int newEarly = parentEarly edgeValue;
if (newEarly > this->early)
this->early = newEarly;
}
void updateLater(int childLater, int edgeValue) {
int newLater = childLater - edgeValue;
if (newLater < this->later)
this->later = newLater;
}
};
class Graph {
public:
vector<Vertex> vertexes;
vector<vector<int> > adjMat;
int n;
public:
void readVertexes() {
//TODO: 将顶点数读入成员变量n
//TODO： 从输入初始化vertexes数组
int i=0;
for(; i<n; i) {
Vertex v(i);
this->vertexes.push_back(v);
}
//为成员变量adjMat创建内存，赋初值
for(i=0; i<n; i) {
vector<int> row;
int j=0;
for(; j<n; j) {
//TODO： 将0增加到row最后
}
//TODO： 将row增加到adjMat最后
}
}
void readAdjMatrix() {
//read the adjacent info into this->adjMat
int edges;
cin >> edges;
int i=0;
int s, t, w; //s源顶点编号，t目的顶点编号，w边长
for(; i<edges; i) {
//TODO: 读入s,t,w，并将adjMat的第s行、第t列的值改为w.
}
}
void updateEarly(int parentNo, queue<int>& earlyQue) {
int parentEarly = vertexes[parentNo].early; //读入父结点early值
int j=0;
for(; j<n; j) {
int edgeValue = adjMat[parentNo][j];
if (edgeValue == 0) continue; //若父结点与结点j没有边相连，pass
Vertex& child = vertexes[j];
child.updateEarly(parentEarly, edgeValue); //更新子结点j的early信息
if(!child.hasEnterQueue) {
child.hasEnterQueue = true; //将子结点加入队列
earlyQue.push(j);
}
}
}
void updateLater(int childNo, queue<int>& laterQue) {
//TODO:
}
int getRoot() {
//获取入度为0的顶点
int j=0;
for(; j<n; j) {
int i=0;
for(; i<n && adjMat[i][j] == 0; i);
if (i>=n) return j; //j has not any in-edges.
}
return -1; //表示没找到
}
int getLeaf() {
//TODO： 获取出度为0的顶点
}
void printEarlyLater(bool isEarly) {
int i=0;
for(; i<n; i) {
Vertex& v = vertexes[i];
if (isEarly)
cout << v.early << " ";
else {
cout << v.later << " ";
}
}
cout << endl;
}
void findEarly() {
//执行关键路径算法，求每个顶点的最早开始时间。
int r = getRoot();
Vertex& root = vertexes[r];
root.hasEnterQueue = true;
root.early = 0;
queue<int> que;
que.push(r);
while(!que.empty()) {
int p = que.front();
que.pop();
updateEarly(p, que);
}
printEarlyLater(true);
}
void clearEnterQueue() {
int i=0;
for(; i<n; i) {
vertexes[i].hasEnterQueue = false;
}
}
void findLater() {
//TODO：调用clearEnterQueue，以清除每个顶点的hasEnterQueue=false
//执行关键路径算法，求每个顶点的最迟开始时间。
}
void main() {
readVertexes();
readAdjMatrix();
findEarly();
findLater();
}
};
int main() {
int t=1;
//cin >> t;
while (t--) {
Graph g;
g.main();
}
return 0;
}输入
第一行图的顶点总数
第二行边的总数
第三行开始，每条边的时间长度，格式为源结点 目的结点 长度
输出
第一行：第个顶点的最早开始时间
第二行：每个顶点的最迟开始时间
输入样例1
9 12 0 1 3 0 2 10 1 3 9 1 4 13 2 4 12 2 5 7 3 6 8 3 7 4 4 7 6 5 7 11 6 8 2 7 8 5
输出样例1
0 3 10 12 22 17 20 28 33 0 9 10 23 22 17 31 28 33
思路分析
它给的代码是存在严重缺陷的，不能用。
AC代码
代码语言：javascript复制#include<iostream>
using namespace std;
const int max_number=200;
int main(){
int vertex_number,edge_number,origin,terminal;
cin>>vertex_number>>edge_number;
int matrix[max_number][max_number]={0};
int inDegree[max_number]={0};
int topology[max_number];
for(int i=0;i<edge_number;i ){
cin>>origin>>terminal;
cin>>matrix[origin][terminal];
}
for(int i=0;i<edge_number;i )
for(int j=0;j<edge_number;j )
if(matrix[j][i])
inDegree[i] ;
int count=0; //topology sort
while(count<vertex_number){
for(int i=0;i<vertex_number;i )
if(inDegree[i]==0){
topology[count ]=i;
inDegree[i]=-1;
for(int j=0;j<vertex_number;j )
if(matrix[i][j])
inDegree[j]--;
}
}
int anti_topology[max_number];
for(int i=0;i<vertex_number;i )
for(int j=0;j<vertex_number;j )
if(i==topology[j])
anti_topology[i]=j;
int ve[max_number]={0};
int vl[max_number]={0};
int vve[max_number]={0};
int vvl[max_number]={0};
for(int i=1;i<vertex_number;i ){
int max=0;
for(int j=0;j<vertex_number;j )
if(matrix[j][topology[i]]&&matrix[j][topology[i]] ve[anti_topology[j]]>max)
max=matrix[j][topology[i]] ve[anti_topology[j]];
ve[i]=max;
vve[topology[i]]=max;
}
vvl[topology[vertex_number-1]]=vl[vertex_number-1]=ve[vertex_number-1];
for(int i=vertex_number-2;i>=0;i--){
int min=0x3f3f3f3f;
for(int j=0;j<vertex_number;j )
if(matrix[topology[i]][j]&&vl[anti_topology[j]]-matrix[topology[i]][j]<min)
min=vl[anti_topology[j]]-matrix[topology[i]][j];
vl[i]=min;
vvl[topology[i]]=min;
}
for(int i=0;i<vertex_number;i )
cout<<vve[i]<<' ';
cout<<endl;
for(int i=0;i<vertex_number;i )
cout<<vvl[i]<<' ';
}
