当前位置：首页 > article >正文

算法设计与分析-上机实验10

article 2024/11/23 8:23:17

1、已知一个加权有向图（为了计算方便，假设编号为1的顶点是入度为0的源点，编号为n的顶点是出度为0的汇点，图中的顶点从1开始编号），要求计算图中从源点出发到汇点的最短距离及其对应的路径（逆向输出）。

输入

第1行输入两个整数，分别表示图G中顶点数n和边数m。
第2 - m+1行每行输入三个整数，分别表示顶点i和顶点j的编号以及由这两个顶点的有向边上的权。

输出

第1行输出源点到汇点的最短路径距离。
第2行输出汇点到源点的逆向最短路径。

样例输入

样例输出

60
5 3 4 1

代码

// By SnowDream
#include<bits/stdc++.h>
using namespace std;

const int MaxSize = 100;
int n;  // 图中的顶点个数
int m;  // 图中的边的个数
vector<vector<int>> a(MaxSize, vector<int>(MaxSize, INT_MAX)); // 邻接矩阵
vector<int> label(MaxSize, 0); // 存储源点到其余顶点最短路径上的最后一个顶点编号
vector<int> d(MaxSize, INT_MAX); // 存储从源点出发到其余各个顶点的最短距离

void CreateGraph() {
    int u, v, w;
    for (int i = 1; i <= n; i++) { // 初始化邻接矩阵对角线
        a[i][i] = 0;
    }
    for (int i = 0; i < m; i++) { // 输入边信息填写有向图的邻接矩阵
        cin >> u >> v >> w;  // 边的信息包括顶点1和顶点2的编号以及它们之间的距离
        a[u][v] = w;
    }
}

void snow() { // 从顶点1开始
    queue<pair<int, int>> q; // 使用STL中的队列，队列元素是一个整数对，表示顶点编号和当前距离
    q.push({1, 0}); // 构造根节点

    while (!q.empty()) {
        auto e = q.front();
        q.pop();

        int i = e.first;
        int length = e.second;
        for (int j = 1; j <= n; j++) {
            if (a[i][j] < INT_MAX && length + a[i][j] < d[j]) {
                d[j] = length + a[i][j];
                label[j] = i;
                q.push({j, d[j]});
            }
        }
    }
}

int main() {
    cin >> n >> m;
    CreateGraph();
    d[1] = 0;
    label[1] = 0;
    snow();
    cout << d[n] << endl;
    for (int i = n; i != 0; i = label[i]) {
        cout << i << " ";
    }
    return 0;
}

2、给定n种物品和一背包。物品i (1≤i≤n) 的重量是wi (wi > 0)，其价值为vi (vi > 0)，背包的容量为c (c > 0)。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

输入

第1行输入两个整数分别表示物品的数量和背包容量。
第2行输入n个整数分别表示每个物品的重量。
第3行输入n个整数分别表示每个物品的获利。

输出

第1行输出整个背包的最大获利。

样例输入

3 50
45 25 25
28 15 15

样例输出

代码

// By SnowDream
#include<bits/stdc++.h>
using namespace std;

const int MaxSize = 100;
int n; // 物品数量
int c; // 背包容量
vector<int> w(MaxSize); // 各个物品的重量，0号单元不用
vector<int> v(MaxSize); // 各个物品的价值，0号单元不用
vector<int> bestx(MaxSize); // 当前最优解，0号单元不用
int bestv = 0; // 当前最优值
struct QNode {
    int cw; // 当前已放物品的重量
    int cv; // 当前已放物品的获利
    int i; // 当前在解空间树中的层数，假设根结点是第1层
    vector<int> x; // 当前解向量
};
void snow() {
    queue<QNode> q;
    // 构造根结点
    QNode e;
    e.cw = 0;
    e.cv = 0;
    e.i = 1;
    e.x.resize(n + 1, 0); // 初始化解向量
    q.push(e);
    while (!q.empty()) {
        QNode current = q.front();
        q.pop();
        if (current.i == n + 1) { // 处理解空间树中的叶子结点
            if (current.cv > bestv) {
                bestv = current.cv;
                bestx = current.x;
            }
        } else { // 处理解空间树中的非叶子结点
            // 处理左孩子，要该物品
            QNode leftChild = current;
            leftChild.x[leftChild.i] = 1; // 选择当前物品
            leftChild.cw += w[leftChild.i]; // 更新当前重量
            leftChild.cv += v[leftChild.i]; // 更新当前价值
            leftChild.i++; // 准备好进入下一层
            if (leftChild.cw <= c) { // 如果满足约束条件
                q.push(leftChild);
            }
            // 处理右孩子，不要该物品
            QNode rightChild = current;
            rightChild.i++; // 准备好进入下一层
            q.push(rightChild);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> c;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    snow();
    cout << bestv << endl;
    return 0;
}

查看全文

http://www.kler.cn/a/403915.html