一个有关程序运行时间的有趣的问题

P3376 【模板】网络最大流

yiming564 @ 2024-04-06 17:14:05

我写了一个最为简单的 Ford-Fulkerson 算法,但发现在我自己的电脑和在洛谷的服务器上运行有着极大的时间差距。

具体而言,在 #7 测试点,我的算法耗时 322ms,但我下载了 #7 数据并在我的电脑上进行了测试,耗时高达 1.404s。

我的电脑 CPU 是 13700kf,并超频至单核 5.8Ghz,在运行程序时我也使用了 Process Lasso 将程序锁定在大核上运行,原则上单核性能绝对强于洛谷的服务器。

编译器使用的是 GCC 11.4.0,原则上更新的编译器优化应该会更好更完善(

程序运行在 WSL 上

#include <bits/extc++.h>

#define inline __always_inline

void read(int &x)
{
    char ch = getchar();
    while (!isdigit(ch))                        ch = getchar();
    for (x = 0; isdigit(ch); ch = getchar())    x = x * 10 + ch - '0';
}

void read(uint64_t &x)
{
    char ch = getchar();
    while (!isdigit(ch))                        ch = getchar();
    for (x = 0; isdigit(ch); ch = getchar())    x = x * 10 + ch - '0';
}

struct edge_t
{
    uint64_t v, w;
};

int n, m, s, t;
uint64_t u, v, w;
std::vector<std::vector<edge_t>> graph;
std::vector<char> visit;

int dfs(uint64_t v = s, uint64_t flow = 0x7fffffff)
{
    visit[v] = 1;
    uint64_t subflow;
    for (auto &&i : graph[v])
    {
        if (visit[i.v] || i.w == 0)
            continue;
        if (i.v == t)
        {
            subflow = std::min(flow, i.w);
            i.w -= subflow;
            graph[i.v].push_back({v, subflow});
            return subflow;
        }
        subflow = dfs(i.v, std::min(flow, i.w));
        if (subflow != 0)
        {
            i.w -= subflow;
            graph[i.v].push_back({v, subflow});
            return subflow;
        }
    }
    return 0;
}

inline uint64_t Ford_Fulkerson()
{
    uint64_t total = 0;
    uint64_t subflow;
    while ((subflow = dfs()) != 0)
    {
        total += subflow;
        visit.assign(n + 1, 0);
    }
    return total;
}

int main()
{
    read(n), read(m), read(s), read(t);
    graph.resize(n + 1);
    visit.resize(n + 1);
    for (int i = 0; i < m; i++)
    {
        read(u), read(v), read(w);
        graph[u].push_back({v, w});
    }
    printf("%lu", Ford_Fulkerson());
    return 0;
}

有没有大佬能够分析为何在我的个人电脑上运行速度远远慢于洛谷的服务器


by XuYueming @ 2024-04-06 17:20:37

@yiming564 提交是否加 O2,本地是否加 O2


by yiming564 @ 2024-04-06 18:02:04

@XuYueming 当然都加了。。。


by fifnmar @ 2024-06-15 22:51:01

用 Profiler 测个速~


|