2024/2/13 图的基础知识 3（拓扑排序）

目录

最长路

P1807 最长路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Divide by three, multiply by two

Problem - 977D - Codeforces

最长路

P1807 最长路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：使用拓扑排序，开两个二维数组，一个数组用来存边，另一个数组用来存边权

题目要求输出从1~n中的最长路，要从2~n遍历一边，删除其他入度为0的点所以要进两次queue

中间编译错误了好几次，编译错误的原因：数组越界或者参数传递出错

完整代码：

#include <bits/stdc++.h>
#define int long long
const int N = 1500 + 10;
std::vector<std::vector<int>> g(N);
std::vector<std::vector<int>> d(N);
int in[N];
int vis[N];
std::queue<int> q;
void bfs() {
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 0; i < g[cur].size(); i++) {
            int next = g[cur][i];
            in[next]--;
            if (in[next] == 0)
                q.push(next);
        }
    }
    q.push(1);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 0; i < g[cur].size(); i++) {
            int next = g[cur][i];
            in[next]--;
            if (in[next] == 0)
                q.push(next);
            vis[next] = std::max(vis[next], vis[cur] + d[cur][i]);
        }
    }
}
signed main() {
    int n, m;
    std::cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        g[u].push_back(v);
        d[u].push_back(w);
        in[v]++;
    }
    for (int i = 2; i <= n; i++) {
        vis[i] = -1e9;
        if (in[i] == 0)
            q.push(i);
    }
    bfs();
    if (vis[n] == -1e9)
        std::cout << -1;
    else
        std::cout << vis[n];
    return 0;
}

Divide by three, multiply by two

Problem - 977D - Codeforces

思路: 拓扑排序

以{4，8，6，3，12，9}为例

可以发现符合题目的有这些：

{4，8}

{3，6}

{6，12}

{9，3}

{12，4}

可以发现，9前面没有连着的数，即入度为0，由于数据很大，所以不能直接暴力存图，存下标就可以了

完整代码：

#include <bits/stdc++.h>
#define int long long
const int N = 110;
std::vector<std::vector<int>> g (N);
int in[10000010];
int a[N];
int n;
std::queue<int> q;
void bfs()
{
    for(int i = 1;i <= n;i ++)
    {
        if(in[i]==0)
            q.push(i);
    }
    while(!q.empty())
    {
        int cur=q.front();
        q.pop();
        std::cout<<a[cur]<<" ";
        for(int i = 0;i < g[cur].size();i ++)
        {
            int next=g[cur][i];
            in[next]--;
            if(in[next]==0)
                q.push(next);
        }
    }
}
signed main()
{
    memset(in,0,sizeof(in));
    std::cin >> n;
    for(int i = 1;i <= n;i ++)
    {
        std::cin >> a[i];
    }
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= n;j ++)
        {
            if(a[i]*2==a[j]||(a[i]%3==0&&a[i]/3==a[j]))
            {
                g[i].push_back(j);
                in[j]++;
            }
        }
    }
    bfs();
    return 0;
}