优化图分析

Question

我在这问题中实现了Floyd算法。然而，由于这是我第一次处理邻接列表，我无法使它的内存效率。

我使用了1000*1000和另一个1000大小的列表，但是我看到了人们被接受的100*100大小的解决方案。如何减少图形数组的大小，或者怎样才能最好地接受图中邻接列表中的输入？

P.S.：我尝试使用向量和映射/对STL，但由于我在STL方面不是很好，如果给出一个非STL解决方案，我将非常高兴。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 1e9
int graph[1000][1000], m[1001], n;  //this is the array which I want to decrease
int main(){
    int u, v, flag=0, testCase = 1;
    while(scanf("%d%d", &u, &v), u||v){

        n = 0;
        memset(m, 0, sizeof(m));

        for(int i = 0; i < 1000; i++)
            for(int j=0; j<1000; j++)
            graph[i][j] = INF;

        if(!m[u])
        m[u] = ++n;

        if(!m[v])
        m[v] = ++n;

        graph[m[u]][m[v]] = 1;
        graph[m[u]][m[u]] = 0;
        graph[m[v]][m[v]] = 0;

        while(scanf("%d%d", &u, &v), u||v){
            if(!m[u])
            m[u] = ++n;

            if(!m[v])
            m[v] = ++n;

            graph[m[u]][m[v]] = 1;
            graph[m[u]][m[u]] = 0;
            graph[m[v]][m[v]] = 0;
        }

        for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);

        double s = 0.0;

        for(int i = 1; i <= n; i++)
        for(int j=1; j<=n; j++)
        s += graph[i][j];
        //cout<<s<<endl;
        s /= (double)n*(n-1);
        //cout<<s<<endl;
        printf("Case %d: average length between pages = %.3lf clicks\n",testCase++,s);
    }
    return 0;
    } 

运行这里

Answer 1

问题陈述链接在上面说：“页码将永远在1到100之间”，我不明白为什么您需要保持大小= 1000，大小= 101应该工作得很好。如果我在这里遗漏了什么，请纠正我。

我修改了你的代码这里

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

#define INF 1e9
#define MAX_SIZE 100

int graph[MAX_SIZE + 1][MAX_SIZE + 1], n, mapping[MAX_SIZE + 1];
int main() {
    int u, v, flag=0, testCase = 1;
    while(scanf("%d%d", &u, &v), u||v){
        for(int i = 1; i <= MAX_SIZE; i++) {
            for(int j = 1; j <= MAX_SIZE; j++) {
                graph[i][j] = INF;
            }
            graph[i][i] = 0;
        }
        int n = 0;
        memset (mapping, 0, sizeof(mapping));
        do {
            if (!mapping[u])
                mapping[u] = ++n;
            if (!mapping[v])
                mapping[v] = ++n;
            graph[mapping[u]][mapping[v]] = 1;
        } while(scanf("%d%d", &u, &v), u||v);

        for(int k = 1; k <= n; k++)
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);

        double s = 0.0;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                s += graph[i][j];
        //cout<<s<<endl;
        s /= (double)n*(n-1);
        //cout<<s<<endl;
        printf("Case %d: average length between pages = %.3lf clicks\n",testCase++,s);
    }
    return 0;
}

Answer 2

使用标准库

我试过使用向量和映射/对STL，但是由于我对STL不太在行，如果给出一个非STL解决方案，我会非常高兴的。

您应该要求一个详细的基于标准库的解决方案("STL“指的是”标准模板库“，标准库的某些部分是它的基础，但它不是标准库)。老实说，这可能需要一些时间在开始，但这是完全值得的。目前，从std::min，您没有使用任何特定于C++的东西.

using namespace std;是邪恶的

using namespace std;可能是你会在互联网上的许多教程中看到的最大的错误。它你不应该这么做，因为它可能会不时地产生名称问题和非常意外的错误。只需将std::放在从标准库导入的每个组件的前面即可。

命令您的标题

这并不重要，但如果按字母顺序排序，您可能会发现检查是否已经包含了一些标头比较容易：

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>

摆脱死代码

您应该尽量避免保留注释掉的代码。无论如何，你可能会在某个时候删除它，因为你不记得你想用它做什么，也不记得它为什么起作用了。

你不需要return 0;在main

的末尾

当程序到达函数main的末尾时，如果它没有找到任何return语句，它就会自动地找到return 0;。请注意，这只适用于main，但在您的示例中，这意味着您可以去掉最后一行。