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/  
一周排行
  • 2013的最后一天,我也做个总结. 这一年,我从学生蜕变为职业人. 这一年,我换了4份工作,上海一份,广州一份,北京2份. 遇到了很多人,我尊敬的,我感恩的,我喜欢的,我不喜欢的. 感谢这些人,让我成长为现在的自己. ...
  • C. Appleman and a Sheet of Paper     Appleman has a very big sheet of paper. This sheet has a form of rectan
  • #!/bin/bash datadir="/mydata/data" sqlconf=/etc/mysql installdir=/usr/local/mysql # 关于安装包大家可以去官网下载 ...
  • 


    		    mail伺服器中sendmail的搭建用法
    Mail服务器简介: 邮件服务器是一种用来负责电子邮件收发管理的设备.它比网络上的免费邮箱
  • 1085 - All Possible Increasing Subsequences   PDF (English) Statistics Forum Time Limit: 3 second(s) Memory
  • ##下载nginx源码: wget http://nginx.org/download/nginx-1.7.8.tar.gz tar -xv -f nginx-1.7.8.tar.gz -C /usr/local/s
  • x:Name標記特性與Name屬性
    本文转载自silvergingko的专栏 在Xaml中定义了一个元素后,如果后面要使用该元
  • package main import ( "bytes" "compress/zlib" "fmt" "io" "os&qu ...
  • zw版轉發&#183;台灣nvp系列Delphi例程HALCON SetIcon2
    zw版[转发·台湾nvp系列Delphi例程]HALCON SetIcon2   proc ...
  • 1.下载地址(注册:jackchn,[email protected]) http://windows.github.com/ 2.使用 github for Windows使用介绍 搭建一个免费的,无限流量的B ...