Comment

09023310: 2024-10-08 20:20:27

BFS求最大长度路径 
#include<iostream>
#include<vector>
#include<queue>

using namespace std;

bool isValid(vector<vector<int>> map, int i, int j) {
    if (i < 0 || j < 0 || i > map.size() || j > map[0].size() || map[i][j] == -1) {
        return false;
    }
    return true;
}

int leaveTime(vector<vector<int>> map, int n) {
    vector<int> distance(n, -1); // 从0点出发到各点距离，初始化为-1
    distance[0] = 0;
    queue<int> que = {};

    vector<int> in_degree(n, 0); // 计算入度

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (isValid(map, i, j)) {
                in_degree[j]++;
            }
        }
    }

    // 将入度为 0 的点设为起始点
    for (int j = 0; j < n; j++) {
        if (!in_degree[j]) {
            que.push(j);
        }
    }

    // 广度优先搜索
    while (!que.empty()) {
        int temp = que.front();
        que.pop();
        for (int j = 0; j < n; j++) {
            if (isValid(map, temp, j)) {
                distance[j] = max(distance[j], distance[temp] + map[temp][j]); // 计算较大距离
                in_degree[j]--;
                if (!in_degree[j]) {
                    que.push(j); // 如果入度为0，加入队列
                }
            }
        }
    }

    return distance[n - 1];
}

int main() {
    int T;
    cin >> T;
    vector<int> ans = {};
    while (T--) {
        int n;
        cin >> n;
        vector<vector<int>> map(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int temp;
                cin >> temp;
                map[i][j] = temp;
            }
        }
        ans.push_back(leaveTime(map, n));
    }

    for (int i : ans) {
        cout << i << endl;
    }
}

RockyChen0205: 2023-12-15 12:11:43

AOE图的关键路径，代码如下：

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

using namespace std;
int main(){
	int T=0; //t行
	cin>>T;
	for(int t=0;t<T;t++){
		int n;
		cin>>n;
		vector<vector<int>> map(n,vector<int>(n,0));
		vector<int> count(n,0);  //拓扑排序过程中使用
		vector<int> ee(n,0);  //时间最早发生时间
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				cin>>map[i][j];
				if(map[i][j]!=-1)
					count[j]++;  //数有j这个节点有多少个前驱结点
			}
		}
		queue<int> q;   
		vector<int> top;
		q.push(0);
		//拓扑排序
		while(!q.empty()){
			int p=q.front();
			q.pop();
			top.push_back(p);
			for(int i=0;i<n;i++){
				if(map[p][i]!=-1){
					count[i]--;
					if(count[i]==0) q.push(i);
				}
			}
		}
		
		for(auto t: top){
			int length=ee[t];  
			for(int i=0;i<n;i++){
				if(map[t][i]!=-1){
					int a=map[t][i];
					if(a+length>ee[i]){
						ee[i]=a+length;
					}
				}
			}
		}
		
		cout<<ee[n-1]<<endl;

	}
}