小工具知识网

当前位置: 首页 > 行业知识 > 图论入门题题解

行业知识

图论入门题题解

2026-11-18 15:18:34 来源:互联网转载

✨���迎来到脑子不好的小菜鸟的文章✨

      创作不易,麻烦点点赞哦

          所属专栏:刷题_脑子不好的小菜鸟的博客-CSDN博客

          我的主页:脑子不好的小菜鸟

          文章特点:关键点和步骤讲解放在

          代码相应位置

拓扑排序 / 家谱树

https://vjudge.net/contest/613618#problem/A

//拓扑排序:找到入度为0的点,将其写入答案,再删去其箭头,再继续找入度为0的点,循环往复vectoredeg[101];int n, deg[101] = { 0 };//入度void init()//建图{    cin >> n;    int i, val;    for (i = 1; i > val && val != 0)        {            edeg[i].push_back(val);            deg[val]++;        }    }}void toposort()//拓扑排序{    int i;    queue que;    for (i = 1; i > s;    int i;    //初始化ans    for (i = 1; i  u >> v >> w;        add(u, v, w);    }    int pos = s;//初始化pos为s    while (visit[pos] == 0)    {        int minn = INT_MAX;//注意更新        visit[pos] = 1;//标记        //更新儿子的最短路径        for (i = head[pos]; i != 0; i = edge[i].next)        {            if (visit[edge[i].to] == 0 && ans[edge[i].to] > ans[pos] + edge[i].wei)                ans[edge[i].to] = ans[pos] + edge[i].wei;        }        //找最短路径        for (i = 1; i > m >> s;    for (i = 1; i  u >> v >> w;        add(u, v, w);    }    priority_queueque;//距离,点    que.push({0, s});    while (!que.empty())    {        int qh = que.top().first;        int h = que.top().second;        que.pop();/*记得pop()!!!!!!!!!*/        if (visit[h] == 0)        {            visit[h] = 1;            for (i = head[h]; i != 0; i = edge[i].next)//不断找下一个儿子,直到找完            {                if (ans[edge[i].to] > ans[h] + edge[i].wei)                {                    ans[edge[i].to] = ans[h] + edge[i].wei;                    if (visit[edge[i].to] == 0)                        que.push({ -ans[edge[i].to], edge[i].to });                }            }        }    }    for (i = 1; i  n >> m;    for (i = 1; i > v >> w;        if (w 

上一篇:独享服务器怎么托管

下一篇:微OA源码深度解析,揭秘高效协同办公的底层逻辑秘密