P1113 [USACO02FEB] 杂务

链接

这是一道拓扑排序变种题,每个杂物可能有前置条件(也就是入度),完成前置条件才可以向下进行

我们可以设置一个node={st,time,to}结构体,代表起始时间,持续时间,和指向的其他节点

用邻接表储存vectorg[N],这里我将g[i][0]来储存i节点的信息(只有st和time有效),后续存储指向的其他节点(只有to有效)

给每个节点的st赋值要注意取最大值(毕竟要完成所有的前置才可以进行)

代码如下:

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N = 1e5 + 10;
struct node {
	int st = 0;
	int time = 0;
	int to;
};
vector<node>g[N];
vector<int>inde(N,0);
int n;
void bfs() {
	queue<int>q;
	for (int i = 1;i <= n;i++) if (!inde[i]) q.push(i);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		int cur_t = g[cur][0].st;
		int len = g[cur][0].time;
		for (int i = 1;i < g[cur].size();i++) {
			int to = g[cur][i].to;
			g[to][0].st = max(g[to][0].st, cur_t + len);
			inde[to]--;
			if (!inde[to]) q.push(to);
		}
	}
	int ans = 0;
	for (int i = 1;i <= n;i++) {
		ans = max(g[i][0].st + g[i][0].time, ans);
	}
	cout << ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 1;i <= n;i++) {
		int idx, len;
		cin >> idx >> len;
		g[i].push_back({ 0,len });
		int to;
		while (cin >> to && to) { g[to].push_back({ 0,0,i });inde[i]++;}
	}
	bfs();
}

时间复杂度:O(n+m)

空间复杂度:O(n+m)