亚线性的近似最小支撑树

问题

自己给出ϵ的值并带入计算

算法过程

代码

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <queue>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define QueueSize 1000

class Env
{
public:
    vector<vector<int>> graph;
    Env()
    {
        graph = getGraph("rand2_2.csv"); //rand1_1.csv rand1_2.csv rand1_3.csv rand2_1.csv rand2_2.csv 共5个测试用例
    }

    vector<vector<int>> getGraph(string file_path)
    {
        vector<vector<int>> user_arr;
        ifstream fp(file_path);
        string line;
        while (getline(fp, line))
        {
            vector<int> data_line;
            string number;
            istringstream readstr(line);
            for (int j = 0; j < 33; j++)
            {
                getline(readstr, number, ',');
                data_line.push_back(atoi(number.c_str()));
            }
            user_arr.push_back(data_line);
        }
        return user_arr;
    }
};

// 所有的代码都需要写在 Algo 类内，自行定义其他需要的变量或函数
class Algo
{
public:
    Algo()
    {
        cout << "algo ok" << endl;
    }

    typedef struct
    {
        int front;
        int rear;
        int count;
        int data[QueueSize];
    } Queue;

    void InitQueue(Queue *M)
    {
        M->front = M->rear = 0;
        M->count = 0;
    }

    int QueueEmpty(Queue *M) 
    {
        if (M->count == 0)
            return 1;
        else
            return 0;
    }

    void EnQueue(Queue *M, int x) 
    {
        M->count++;
        M->data[M->rear] = x;
        M->rear = (M->rear + 1) % QueueSize;
    }

    int DeQueue(Queue *M) 
    {
        int temp;
        temp = M->data[M->front];
        M->count--;
        M->front = (M->front + 1) % QueueSize;
        return temp;
    }
    double cnum(vector<vector<int>> graph)
    {
        Queue M;
        InitQueue(&M);
        double a = 0.1;
        double b[1000];
        double n;
        n = 2 / a;
        srand((unsigned)time(NULL));
        for (int k = 1; k < 61; k++) //取样60个数
        {
            InitQueue(&M);
            int visited[33];
            for (int m = 0; m < 33; m++)
                visited[m] = 0;
            int i = rand() % 33;
            visited[i] = 1;
            EnQueue(&M, i);
            double t = 1;
            while (!QueueEmpty(&M))
            {
                i = DeQueue(&M);
                for (int j = 0; j < 33; j++)
                {
                    if (double(j) <= double(n))
                    {
                        if (graph[i][j] > 0 && visited[j] == 0)
                        {
                            t = double(t + 1);
                            visited[j] = 1;
                            EnQueue(&M, j);
                        }
                    }
                }
            }

            if (t != 0)
            {
                b[k] = double(1 / t);
            }
            else
            {
                b[k] = 0;
            }
        }
        double sum;
        for (int k = 1; k < 61; k++)
        {
            sum = b[k] + sum;
        }
        sum = sum / 60 * 33;
        cout << "连通分量：" << sum << endl;
        return sum;
    }
    int run(Env env)
    {
        //在此写入你的代码  env.graph 为目标矩阵
        int w = 0;
        for (int i = 1; i < 33; i++)
        {
            for (int j = 0; j < 33; j++)
            {
                if (w < env.graph[i][j])
                {
                    w = env.graph[i][j];
                }
            }
        }
        cout << "最大权重:" << w << endl;
        double sums, W;
        double n = 33;
        for (int n = 0; n < w-1; n++)
        {
            for (int i = 0; i < 33; i++)
            {
                for (int j = 0; j < 33; j++)
                {
                    if (env.graph[i][j] = w - n)
                    {
                        env.graph[i][j] == 0;
                    }
                }
            }
            sums = double(sums + cnum(env.graph));
        }
        cout <<"连通分量总和"<< sums << endl;
        W = double(n - w + sums);
        cout << "最优解:" << W << endl;

        return 0; //修改为返回正确的结果
    }
};

int main()
{
    Algo algo;
    Env env;
    time_t start = clock();
    algo.run(env);
    time_t end = clock();
    cout << "程序耗时: " << double(end - start) / CLOCKS_PER_SEC << " ms" << endl;
    cout << "占用内存：" << sizeof(algo) << " byte" << endl;
    return 0;
}

结果