题解 | #任务安排#

学习笔记

//非常漂亮地把可能的雷都踩了，算是吃了这类题的教训

//参考了大佬的思路

//萌新代码 谨慎观看

/*2024.2.21 邻接表*/
//怎么知道什么时候可以拖延？
//先拓扑找到最早结束时间，记录排序
//根据排序，反向回溯求出最晚结束时间
//WA: 检测是否为重复路径问题
//WA: 也不是输出字典序问题
//WA: 其实最关键的错误是没有处理好不与任何点产生链接的孤立点
//ps：后面测试了一下，前俩个WA猜测都不会导致WA，不过，小心为上~
#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
int n, m;
const int N = 3e5 + 10;
struct Node {
	int late = 0x3f3f3f3f;
	int zao;
	int cost;
	int in = 0;
}node[N];

vector<int> arr[N];

int main() {
	ios::sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> node[i].cost;
		node[i].zao = node[i].cost;
	}
	map<pair<int, int>, bool> g;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		if (g[{u, v}]) continue;
		g[{u, v}] = 1;
		arr[u].push_back(v);
		node[v].in++;
	}
	queue<int> q;
	//priority_queue<int> pq;
	vector<int> qq;
	for (int i = 1; i <= n; i++) {
		if (node[i].in == 0) {
			q.push(i);
		}
	}
	int tim = 0;
	while (q.size()) {
		int pos = q.front();
		q.pop();
		qq.push_back(pos);//其实是把数组当栈表用了
		tim = max(tim, node[pos].zao);//找出最少所需时间
		for (int i = 0; i < arr[pos].size(); i++) {
			int x = arr[pos][i];
			node[x].in--;
			node[x].zao = max(node[x].zao, node[x].cost + node[pos].zao);//最早结束时间
			if (node[x].in == 0) {
				q.push(x);
			}
		}
	}
	if (qq.size() != n) {
		cout << -1 << "\n";
		return 0;
	}
	for (int i = n-1; i >= 0; i--) {
		int pos = qq[i];
		node[pos].late = tim;//处理孤立点和没出度的点
		for (int i = 0; i < arr[pos].size(); i++) {
			int to = arr[pos][i];
			int cost = node[to].cost;
			node[pos].late = min(node[to].late - cost, node[pos].late);
		}
	}
	vector<int> ans;
	for (int i = 1; i <= n; i++) {
		if (node[i].late > node[i].zao) ans.push_back(i);
	}
	sort(ans.begin(), ans.end());
	cout << ans.size() << "\n";
	for (int i : ans) {
		cout << i << " ";
	}cout << "\n";
	return 0;
}