POJ 3249 拓撲排序+DP

貌似是道水题。TLE了几次。把所有的输入输出改成scanf 和 printf ,有吧队列改成了数组模拟。然后就AC 了。2....

Description:

MR.DOG 在找工作的过程中呢。遇见了这样一个问题。有n个城市,m条小道。然后要从入度为0的点出发,出度为0的点结束,中途经过的城市呢,都是要付费的。负数表示花费。正数表示收益。然后让你求收益最大或者说花费最少的总值。

貌似。BFS和DFS都会超时。不妨一试。附代码:

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
#define maxn 105
#define maxm 1005
#define inf 2100
using namespace std;

struct Arc
{
    int point;
    int next_arc;
};
//node 存储每个顶点,arc存储每条边。node[i]表示第i个顶点指向的第一条边在arc中的位置。next_arc表示和这条边同样出发点的下一条边在arc中的位置。
Arc arc[maxm];
int node[maxn], val[maxn];
//ind 和 outd 数组表示顶点的入度和出度 dp数组表示到达每个点的的最大收益
int ind[maxn], outd[maxn], dp[maxn];
// 数组模拟队列 tot表示总共加入的边的数量
int tot, front, rear;
int q[maxn];

void insert(int u, int v)    // 加入从u指向v的一条边
{
    arc[tot].next_arc = node[u];
    arc[tot].point = v;
    node[u] = tot++;
}

void init()
{
    tot = 0;
    memset(node, -1, sizeof(node));
    memset(ind, 0, sizeof(ind));
    memset(outd, 0, sizeof(outd));
}

void topsort()  // 拓扑排序+DP
{
    while(front <= rear)
    {
        int x = q[front++];
        for (int e=node[x]; e!=-1; e=arc[e].next_arc)
        {
            int temp = arc[e].point;
            ind[temp]--;
            dp[temp] = max(dp[temp], dp[x] + val[temp]);
            if (ind[temp] == 0)
            {
                q[++rear] = temp;
            }
        }
    }
}

int main()
{
    int n, m, x, y;
    while(~scanf("%d%d", &n, &m))
    {
        init();
        front = 0, rear = -1;
        for (int i=1; i<=n; ++i)
        {
            scanf("%d", &val[i]);
        }
        for (int i=0; i<m; ++i)
        {
            scanf("%d%d", &x, &y);
            insert(x, y);
            ind[y]++;
            outd[x]++;
        }
        for (int i=1; i<=n; ++i)
        {
           dp[i] = -inf;
        }
        for (int i=1; i<=n; ++i)
        {
            if (ind[i] == 0)
            {
                q[++rear] = i;
                dp[i] = val[i];
            }
        }
        topsort();
        int ans = -inf;
        for (int i=1; i<=n; ++i)
        {
            if (outd[i] == 0)
            ans = max(ans, dp[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

更多相关文章
  • http://poj.org/problem?id=3249 题意: 给一个有向无环图DAG(不一定联通),每个点有权值,入度为0的点为起点,出度为0的点为终点,选择一个起点走到一个终点,使得路上的权和最大. 分析: dp[to] = max(dp[from]) + value[to],然后先拓扑排
  •        Description Windy has N balls of distinct weights from 1 unit to N units. Now he tries to label them
  • Description An ascending sorted sequence of distinct values is one in which some form of a less-than operato
  • /* (⊙v⊙)嗯 貌似是一个建图 拓扑+深搜的过程.至于为什么要深搜嘛..一个月前敲得题现在全部推了重敲,于是明白了.因为题意要求如果有多个可能的解的话. * 就要输出字典序最小的那个.所以可以对26个英文字母从小
  • 無前趨的頂點優先的拓撲排序方法(JAVA)(轉載http://128kj.iteye.com/blog/1706968)
    无前趋的顶点优先的拓扑排序方法     该方法的每一步总是输出当前无前趋(即人度为零)的顶
  • poj 2762(強連通分量+拓撲排序)
    题目链接:http://poj.org/problem?id=2762 题意:给出一个有向图,判断任意的两个顶点(u,v)能否从u到达v,或v到达u,即单连通,输出Yes或No. 分析:对于同一个强连通分量而言,所有的点都是互达的,如果该有向图只有一个强连通分量,则肯定是Yes了: 若有多个强连通分
  •   题目传送门 1 /* 2 拓扑排序裸题:有三种情况: 3 1. 输入时发现与之前的矛盾,Inconsistency 4 2. 拓扑排序后,没有n个点(先判断cnt,即使一些点没有边连通,也应该是n,此时错误是有环
  • 题目链接:http://poj.org/problem?id=1270 思路:就是一简单的dfs+拓扑排序,然后就是按字典序输出所有的情况. http://paste.ubuntu.com/5987294/  
一周排行
  • 算法思想:由于二叉排序树的中序遍历可以得到一个有序的序列,因此,我们可以使用中序遍历进行求解. 代码如下: 1 #include <stack> 2 using namespace std; 3 4 ty ...
  • 


    		    專家分享從數據包談如何封殺P2SP類軟件
    [专家分享]从数据包谈如何封杀P2SP类软件 我们经常在用户的网络中发现大量的P2P应用,
  • SQLServer學習筆記系列11
    一.写在前面的话 身体是革命的本钱,这句放在嘴边常说的话,还是拿出来一起共勉,提醒一起奋斗
  • 看看下面的程序的输出: #include <stdio.h>char *returnStr(){    char *p="hello world!";    return p;}int ...
  • linux下安装完成mysql后,远程调用出现远程访问被拒绝.查找了相关解决方法后,直接不能使用root在本地登录了. 出现 ERROR 1044 (42000):ccess denied for user 'roo
  • Solaris 8 或 9 OS 启用多路径:在运行 Solaris OS 8 或 9 的主机上启用多路径软件: 1. 使用文本编辑器打开 /kernel/drv/scsi_vhci.conf 文件. 2. 在文件中
  • 转自:http://blog.sina.com.cn/s/blog_af26e010194ht.html 最近修改oracle触发器,在过程中遇到两个问题: select lastname from hrmresou ...
  • 待完成  http://www.gtan.com/akka_doc/ http://my.oschina.net/mingdong/blog/297972   http://www.jdon.com/concurre
  • stackoverflow用户对添加libxml2库表现出了极大的抱怨 ,原因在要把它好好地添加进去实在是太复杂了. 我就是因为出现了'libxml/tree.h file not found’错误,才发现的这篇贴子 ...
  • 前一篇文章写过了如何合成并压缩大批量文件,这篇文章解释一下如何在拿到压缩文件后如何解压并还原大批量文件.   解压缩的JCL很简单,如下所示,和压缩的JCL类似,只要把参数改成UNPACK,然后设置一下infile和 ...