洛谷P1137 旅行计划

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题解

别问我为什么写这么水的题解,问就是为了那门水的不行的专业选修课。

很简单,这个图肯定是个DAG(请不要问为什么,自己看一下题目描述。。。)

然后我们在这个DAG上按拓扑序来进行DP就可以了,因为入度为0的点一定最多游览一个,然后不断类似SPFA最长路一样的进行DP,就可以求出到某个城市最多可以游览的城市数目了。

代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<3) + (num<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
int n,m;
int x,y;
const int maxn = 1e5+5;
vector<int>g[maxn];
int f[maxn],d[maxn];
int inq[maxn];
int main(){
    memset(d,0,sizeof(d));
    n = get_num();
    m = get_num();
    for(int i = 1;i <= m;++i){
        x = get_num();
        y = get_num();
        g[x].push_back(y);
        d[y]++;
    }
    queue<int>q;
    for(int i = 1;i <= n;++i){
        if(!d[i])
            q.push(i),inq[i] = 1;
        f[i] = 1;
    }
    while(!q.empty()){
        int x = q.front();
        q.pop();
        inq[x] = 0;
        for(int i = 0;i < g[x].size();++i){
            int v = g[x][i];
            f[v] = max(f[v],f[x] + 1);
            if(!inq[v]){
                inq[v] = 1;
                q.push(v);
            }
        }
    }
    for(int i= 1;i <= n;++i){
        printf("%d\n",f[i]);
    }
    return 0;
}


Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00