POJ Test for Job(DAG上拓扑排序)

题目链接:http://poj.org/problem?id=3249

       题意是给了n个点,m条边(单向边),然后每个点都有一个点权(存在负权),问从入度为0的点开始到出度为0的点,最大的权值和为多少。

       题目中说了这是一个DAG图(有向无环图),跑最长路的话会超时(spfa反向建边好像可以过),根据有向无环图的性质我们可以用拓扑排序来写,根据每条边的度数来选择边的顺序从而更新最长路的值。


AC代码:

// #include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 100005
#define maxm 1000005
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
struct Node{
  int to,next;
}Edge[maxm];
int head[maxn],num;
int n,m;
int depi[maxn], pre[maxn], depo[maxn];
ll dist[maxn];

void init(){
  for(int i=0;i<=n;i++){
    depi[i] = depo[i] = 0;
    head[i] = -1;
    dist[i] = -inf;
  }
  num = 0;
}

void add(int u,int v){
  Edge[num].to = v;
  Edge[num].next = head[u];
  head[u] = num ++;
}

void Topo(){
  queue<int> q;
  for(int i=1;i<=n;i++){
    if(depi[i] == 0){
      q.push(i);
      dist[i] = pre[i];
    }
  }
  while(!q.empty()){
    int u = q.front();
    q.pop();
    for(int i=head[u];i!=-1;i=Edge[i].next){
      int v = Edge[i].to;
      dist[v] = max(dist[v], dist[u] + pre[v]);
      if(--depi[v] == 0) q.push(v);
    }
  }
}

int main()
{
  while(~scanf("%d%d",&n,&m)){
    init();
    for(int i=1;i<=n;i++){
      scanf("%d",&pre[i]);
    }
    for(int i=0;i<m;i++){
      int u, v;
      scanf("%d%d",&u, &v);
      add(u, v);
      depi[v] ++;
      depo[u] ++;
    }
    Topo();
    ll ans = -inf;
    for(int i=1;i<=n;i++){
      if(depo[i] == 0) ans = max(ans, dist[i]);
    }
    printf("%lld\n", ans);
  }
  return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券