专栏首页Zaqdt_ACMPOJ Test for Job(DAG上拓扑排序)

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 条评论
登录 后参与评论

相关文章

  • POJ 3020 Antenna Placement(二分图最小边覆盖)

           题意是有一个n*m的地图,图中'*'表示城市,现在要给每个城市覆盖无线,需要安装基站,每个基站最多只能覆盖相邻的两个城市,也就是1*2或者2*1的...

    Ch_Zaqdt
  • NYOJ 116 士兵杀敌(二) (线段树+树状数组)

    题目链接:http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=116

    Ch_Zaqdt
  • 最少联通代价(dfs+曼哈顿距离)

    现在要把这 2 个连通块连通, 求最少需要把几个’.’转变成’X’。上图的例子中, 最少只需要把 3个’.’转变成’X’。下图用’*’表示转化为’X’的格点...

    Ch_Zaqdt
  • 剑指Offer-构建乘积数组

    package Array; import sun.security.util.Length; /** * 构建乘积数组 * 给定一个数组A[0,1,....

    武培轩
  • POJ 3020 Antenna Placement(二分图最小边覆盖)

           题意是有一个n*m的地图,图中'*'表示城市,现在要给每个城市覆盖无线,需要安装基站,每个基站最多只能覆盖相邻的两个城市,也就是1*2或者2*1的...

    Ch_Zaqdt
  • 「CodeForces - 598B」Queries on a String

    字符串s(1 ≤ |s| ≤ 10 000),有m(1 ≤ m ≤ 300)次操作,每次给l,r,k,代表将r位置插入l位置前,执行k(1 ≤ k ≤ 1 00...

    饶文津
  • 初级程序员面试不靠谱指南(三)

    二、指针的好基友的& 1.&的意义。说&是指针的好基友其实不恰当,因为&这个符号在C/C++不止有一种含义,但是因为其经常会和指针一起出现在被问的问题列表上,所...

    一心一怿
  • 15.瀑布流、测量

    六月的雨
  • 1250 Fibonacci数列

    时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Description 定义:f0=...

    attack
  • PTA 7-1 畅通工程之局部最小花费问题(35 分)

    7-1 畅通工程之局部最小花费问题(35 分) 某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城...

    Kindear

扫码关注云+社区

领取腾讯云代金券