用C++语言解决文件里的三个实验题

### 实验题目及解决方案概述

#### 1. 网络布线问题
**问题描述**: 需要在6个城市之间布置通信网络，使所有城市能互相通信，并且总成本最低。

**算法**: 使用Prim算法构建最小生成树 (MST) 来解决这个问题。

**代码实现**:

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max();

void prim(int **cost, int V) {
    vector<int> key(V, INF);
    vector<bool> mstSet(V, false);
    vector<int> parent(V, -1);
    key[0] = 0;
    
    for (int count = 0; count < V - 1; ++count) {
        int u = -1;
        for (int i = 0; i < V; ++i)
            if (!mstSet[i] && (u == -1 || key[i] < key[u]))
                u = i;
        
        mstSet[u] = true;
        
        for (int v = 0; v < V; ++v)
            if (cost[u][v] && !mstSet[v] && cost[u][v] < key[v]) {
                parent[v] = u;
                key[v] = cost[u][v];
            }
    }
    
    cout << "Edge \tWeight\n";
    for (int i = 1; i < V; ++i)
        cout << parent[i] << " - " << i << "\t" << cost[parent[i]][i] << endl;
}

int main() {
    int V = 6;
    int **cost = new int*[V];
    for (int i = 0; i < V; ++i) {
        cost[i] = new int[V];
        fill(cost[i], cost[i] + V, INF);
    }

    cost[0][1] = 10; cost[0][3] = 30; cost[0][4] = 45;
    cost[1][0] = 10; cost[1][2] = 50; cost[1][4] = 40; cost[1][5] = 25;
    cost[2][1] = 50; cost[2][4] = 35; cost[2][5] = 15;
    cost[3][0] = 30; cost[3][5] = 20;
    cost[4][0] = 45; cost[4][1] = 40; cost[4][2] = 35; cost[4][5] = 55;
    cost[5][1] = 25; cost[5][2] = 15; cost[5][3] = 20; cost[5][4] = 55;

    prim(cost, V);

    for (int i = 0; i < V; ++i)
        delete[] cost[i];
    delete[] cost;

    return 0;
}

#### 2. 最快路线问题
**问题描述**: 找出从A点到H点最快的路线，考虑不同路段的速度限制和交通拥堵情况。

**算法**: 使用Dijkstra算法计算最短路径，但这里的“最短”是指时间而不是距离。

**代码实现**:

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

struct Node {
    int vertex;
    double time;
    bool operator<(const Node& other) const {
        return time > other.time;
    }
};

double dijkstra(int start, int end, vector<vector<double>>& graph, vector<vector<double>>& speeds) {
    int n = graph.size();
    vector<double> times(n, numeric_limits<double>::max());
    priority_queue<Node> pq;
    pq.push({start, 0});
    times[start] = 0;

    while (!pq.empty()) {
        Node node = pq.top();
        pq.pop();
        int u = node.vertex;
        double t = node.time;

        if (u == end)
            break;

        for (int v = 0; v < n; ++v) {
            if (graph[u][v] != 0) {
                double travelTime = graph[u][v] / speeds[u][v];
                if (times[u] + travelTime < times[v]) {
                    times[v] = times[u] + travelTime;
                    pq.push({v, times[v]});
                }
            }
        }
    }

    return times[end];
}

int main() {
    int n = 8;
    vector<vector<double>> graph(n, vector<double>(n, 0));
    vector<vector<double>> speeds(n, vector<double>(n, 0));

    graph[0][1] = 9; graph[0][2] = 7; graph[0][3] = 9;
    graph[1][2] = 6; graph[1][4] = 12; graph[1][5] = 12;
    graph[2][3] = 8; graph[2][4] = 9;
    graph[3][4] = 10; graph[3][6] = 10;
    graph[4][5] = 7; graph[4][6] = 8; graph[4][7] = 7;
    graph[5][7] = 9; graph[6][7] = 11;

    speeds[0][1] = 40; speeds[0][3] = 80;
    speeds[1][5] = 40; speeds[3][6] = 30;
    speeds[4][7] = 20; speeds[0][2] = 50;
    speeds[1][2] = 50; speeds[1][4] = 50;
    speeds[2][3] = 50; speeds[2][4] = 50;
    speeds[3][4] = 50; speeds[4][5] = 50;
    speeds[4][6] = 50; speeds[5][7] = 80;
    speeds[6][7] = 80;

    double fastestTime = dijkstra(0, 7, graph, speeds);
    cout << "The fastest route from A to H takes: " << fastestTime << " hours." << endl;

    return 0;
}

#### 3. 汽车加油问题
**问题描述**: 一辆汽车加满油后可以行驶N公里，途中经过多个加油站，目标是最少加油次数到达目的地。

**算法**: 使用贪心策略，每次尽可能多地行驶，直到无法到达下一个加油站或终点。

**代码实现**:

#include <iostream>
#include <vector>
using namespace std;

vector<int> minRefills(vector<int>& stations, int tank, int destination) {
    int numRefills = 0;
    int currentRefill = 0;
    vector<int> refills;

    while (currentRefill <= stations.size() - 1) {
        int lastRefill = currentRefill;
        while (currentRefill <= stations.size() - 1 && stations[currentRefill] - stations[lastRefill] <= tank) {
            currentRefill++;
        }
        if (currentRefill == lastRefill) {
            return {};  // It's not possible to reach the destination
        }
        if (currentRefill <= stations.size() - 1) {
            refills.push_back(stations[lastRefill]);
            numRefills++;
        }
    }

    return refills;
}

int main() {
    int N = 600;
    vector<int> stations = {300, 500, 700, 1100, 1400, 1600, 1900, 2200};
    int destination = 2300;

    vector<int> refills = minRefills(stations, N, destination);

    if (refills.empty()) {
        cout << "It is not possible to reach the destination with the given fuel capacity and stations." << endl;
    } else {
        cout << "You should refill at these stations: ";
        for (int station : refills) {
            cout << station << " ";
        }
        cout << endl;
    }

    return 0;
}

以上代码分别实现了三个实验题的解决方案，使用了Prim算法、Dijkstra算法和贪心策略来解决问题。希望这些代码对你有所帮助！