文章
68
粉丝
691
获赞
26
访问
576.6k
拓扑排序求出最早完成时间和所有任务的最早开始时间,然后反向建图,求出最晚开始时间,两遍拓扑
#define ll long long
#define vec vector<ll>
#define inf 0x3f3f3f3f
#define MAX 500005
#define P pair<ll,ll>
#define MOD 1000000007
int main() {
ll m, n, a[MAX], ind[MAX], x[MAX], y[MAX], f[MAX], g[MAX];
vec G[MAX];
while (cin >> n >> m) {
memset(ind, 0, sizeof(ind));
memset(f, 0, sizeof(f));
fill(g, g + MAX, inf);
for (int i = 1; i <= n; i++)cin >> a[i], G[i].clear();
for (int i = 1; i <= m; i++) {
cin >> x[i] >> y[i]; ind[y[i]]++; G[x[i]].push_back(y[i]);
}
queue<int> q;
int u = -1, v = -1; ll res = 1, cost = 0;
//正向跑拓扑,求出所有点最早开始的时间和最小花费
for (int i = 1; i <= n; i++)if (ind[i] == 0)q.push(i);
while (!q.empty()) {
u = q.front(); q.pop();
for (int i = 0; i < G[u].size(); i++) {
v = G[u][i]; ind[v]--;
//所有条件里最长的那个
if (f[u] + a[u] > f[v])f[v] = f[u] + a[u];
if (ind[v] == 0)
q.push...
登录后发布评论
暂无评论,来抢沙发