icontofig | 发布于 2019-07-07 21:56:00 | 阅读量 262 | topsort DP
发布于 2019-07-07 21:56:00 | topsort DP

题解

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

很简单,这个图肯定是个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;
}



内容更新于: 2019-07-07 21:56:00
链接地址: http://blog.leanote.com/post/icontofig/%E6%B4%9B%E8%B0%B7

上一篇: URL映射 CSP201803 T3

下一篇: BZOJ 3156 防御准备 决策单调性斜率优化DP

262 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航