题解 | #任务安排#

//关键路径的模板题，首先按照拓扑排序的顺序去计算每个点最早的开始时间，在拓扑排序的过程中将节点保存进栈里面
//然后从栈里面挨个的取出，每取出一个去找他的出度边，去计算最晚开始时间。
//最后遍历一遍所有的点，如果最早开始时间和最晚开始时间相等那么就是关键事件。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e5+10;
const int maxnn = 1e5+10;
struct sy{
    int to;
    int next;
    int w;
}edge[maxn];
struct Node{
    int first;
    int late = 0x3f3f;
    int cost;
} node[maxnn];
int head[maxnn];
map<int, int> mp;
int cnt = 0;
int n, m, rt;
//记录入度的个数
int in[maxnn];
stack<int> st;

//构造链式前向星
void add_edge(int u, int v, int w)
{
    edge[++cnt].next = head[u];
    edge[cnt].to = v;
    edge[cnt].w = w;
    head[u] = cnt;
}
//开始进行第一步拓扑排序
bool tuopu()
{
    queue<int> q;
    int num = 0;
    for (int i=1;i<=n;i++)
    {
        if (in[i]==0) 
        {
            q.push(i);
            mp[i] = 1;
        }
    }
    while (q.size())
    {
        int pos = q.front();
        q.pop();
        num ++;
        st.push(pos);
        rt = max(rt, node[pos].first+node[pos].cost);
        for (int i=head[pos];i;i = edge[i].next)
        {
            int next = edge[i].to;
            int w = edge[i].w;
            node[next].first = max(node[next].first, node[pos].first+w);
            in[next]--;
            if (in[next]==0) q.push(next);
        }
    }
    if(num!=n) return false;
    return true;
}

void fanxiang()
{
    while (st.size())
    {
        int pos = st.top();
//         cout<<"pos="<<pos<<endl;
        st.pop();
        node[pos].late = rt-node[pos].cost;
        for (int i=head[pos];i;i = edge[i].next)
        {
            int next = edge[i].to;
            int late = node[next].late;
            int w = edge[i].w;
            node[pos].late = min(node[pos].late, late-w);
        }
    }
}

signed main()
{
    int t, u, v;
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>node[i].cost;
    for (int i=1;i<=m;i++)
    {
        cin>>u>>v;
        in[v]++;
        add_edge(u,v,node[u].cost);
    }
    bool isok = tuopu();
    if (!isok)
    {
        cout<<-1;
        return 0;
    }
//     cout<<"rt="<<rt<<endl;
    fanxiang();
    vector<int> vt;
    for (int i=1;i<=n;i++)
    {
//         cout<<node[i].first<<" "<<node[i].late<<endl;
        if (node[i].late > node[i].first)
        {
            vt.push_back(i);
        }
    }
    cout<<vt.size()<<endl;
    vector<int>::iterator it = vt.begin();
    for (it;it!=vt.end();it++)
    {
        cout<<(*it)<<' ';
    }
    return 0;
}