「Luogu1137」旅行计划

发布于 2018-07-07  215 次阅读


题目

题目描述

小明要去一个国家旅游。这个国家有$ N $个城市,编号为 $ 1 $至$ N $,并且有$ M $条道路连接着,小明准备从其中一个城市出发,并只往东走到城市$ i $停止。

所以他就需要选择最先到达的城市,并制定一条路线以城市$ i $为终点,使得线路上除了第一个城市,每个城市都在路线前一个城市东面,并且满足这个前提下还希望游览的城市尽量多。
现在,你只知道每一条道路所连接的两个城市的相对位置关系,但并不知道所有城市具体的位置。现在对于所有的$ i $,都需要你为小明制定一条路线,并求出以城市$ i $为终点最多能够游览多少个城市。

输入输出格式

输入格式:

第$ 1$行为两个正整数$ N,M $。

接下来$ M $行,每行两个正整数$ x,y$,表示了有一条连接城市$ x $与城市$ y $的道路,保证了城市$ x $在城市$ y $西面。

输出格式:

$ N $行,第$ i $行包含一个正整数,表示以第$ i $个城市为终点最多能游览多少个城市。

输入输出样例

输入样例#1:

[code lang=text]
5 6
1 2
1 3
2 3
2 4
3 4
2 5
[/code]

输出样例#1

[code lang=text]
1
2
3
4
3
[/code]

说明

均选择从城市 $ 1 $ 出发可以得到以上答案。

对于 $ 20\% $ 的数据, $ 1 \le N\le 100$ ;

对于 $ 60\% $ 的数据,$ 1\le N\le 1000 $ ;

对于 $100\%$ 的数据, $ 1 \le N \le 100000,1\le M\le 200000 $ 。

解题报告

这一题是练习拓扑排序的上手简单题目。

首先,这一题可以用DP来做。但是一个不经过拓扑排序的图有后效性。

经过拓扑排序之后按照拓扑序来进行DP即可。

至于如何动态规划:我们考虑拓扑排序完后,只能从东向西走,那么不妨设$ dp_u $表示以节点u为终点,能经过的最多的城市。这就是一个简单的线性dp,状态转移方程为:

$$ dp_u = Max{dp_v}(u和v连通)$$

详情见代码。

代码

#include 
#include 
#include 
#include 

#define add(u,v) node[u].firstEdge = New(&node[u],&node[v])

const int MAXN = 100000 + 5;
const int MAXM = 200000 + 5;

struct Node;
struct Edge;

int N,M,cnt;
Node* ts[MAXN];

struct Node{
    int ru,dp;
    bool used;
    Edge *firstEdge;
}node[MAXN];

struct Edge{
    Node *s,*t;
    Edge *next;
}pool[MAXM],*frog = pool; 

Edge *New(Node *s,Node *t){
    Edge *ret = ++frog;
    ret->s = s;ret->t = t;
    ret->next = s->firstEdge;
    return ret;
} //内存池

inline void topsort(){
    std::queue q;
    for(int i = 1;i <= N;i++)
        if(!node[i].ru){
            q.push(&node[i]);
            ts[++cnt] = &node[i];
        }
    while(!q.empty()){
        Node *v = q.front();q.pop();
        for(Edge *e = v->firstEdge;e;e = e->next){
            if(!--e->t->ru){
                q.push(e->t);
                ts[++cnt] = e->t;
            }
        }
    }
}

int main(){
    scanf("%d%d",&N,&M);
    for(int u,v,i = 1;i <= M;i++){
        scanf("%d%d",&u,&v);
        add(u,v);
        node[v].ru++;
    }
    topsort();
    for(int i = 1;i <= N;i++)
        node[i].dp = 1;
    for(int i = 1;i <= N;i++){
        Node *v = ts[i];
        for(Edge *e = v->firstEdge;e;e = e->next){
            e->t->dp = std::max(e->t->dp,v->dp + 1);
        }
    }
    for(int i = 1;i <= N;i++)
        printf("%d\n",node[i].dp);
    return 0;
}

一个OIer。