山东大学数据结构与算法课程设计实验4网络放大器设置问题

标签：10 课程设计 12 15 int 13 数据结构山东大学 Pmax

问题描述

一个汽油传送网络可由加权有向无环图G表示。图中有一个称为源点的顶点S。从S出发，汽油被输送到图中的其他顶点。S的入度为0，每一条边上的权给出了它所连接的两点间的距离。通过网络输送汽油时，压力的损失是所走距离的函数。为了保证网络的正常运转，在网络传输中必须保证最小压力Pmin。为了维持这个最小压力，可将压力放大器放在网络中的一些或全部顶点。压力放大器可将压力恢复至最大可允许的量级Pmax。令d为汽油在压力由Pmax降为Pmin时所走的距离。在设置信号放大器问题中，需要放置最少数量的放大器，以便在遇到一个放大器之前汽油所走的距离不超过d。编写一个程序来求解该问题。

基本要求

针对网络设计问题考虑使用两种方法解决，并比较两种方法的时间性能，用图表显示比较结果。

数据结构与算法描述

输入Pmax和Pmin的值，还要节点n，以及m为边的个数，进行m个循环，以下m行输入边的起点、终点、每个边减少的石油量。然后对所有的节点进行拓扑排序。

bool topsort(int di[]){
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++){
        if (di[i]==0) q[++tt] = i;
    }
    while (hh <= tt){
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if (--di[j] == 0) q[++tt] = j;
        }
    }
    return tt == n - 1;
}

方案一bfs贪心算法，用bfs进行遍历整个拓扑序列，遍历每个点的邻接点，判断是否存在压力小于Pmin的终点，如果存在将其起点放放大器，将该起点压力改为Pmax,并将压力值更新为原值和现在值中的较大值。如果不存在则只将邻接点的压力值更新为原值和现在值中的较大值。更新为较大值是为了贪心的保证放置的放大器最少。

void bfs(){//贪心
    int hh = 0;
    while (hh <= n - 1){
        //按拓扑序列遍历
        int t = q[hh];
        int flag = 0;
        int minp;
        //检查当前节点是否要放放大器
        for (int i = h[t]; i != -1; i = ne[i]){//遍历与当前节点邻接的点
            int j = e[i];
            minp = p[t] - w[i];
            //最小值检查是否需要放
            if (minp < Pmin){
                flag = 1;
                break;
            }
        }
        //所有与当前节点连接的结点的压力值更新
        if (flag == 0) {
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                p[j] = max(p[j], p[t] - w[i]);
            }
        }
        if (flag == 1) {
            ans++;
            p[t] = Pmax;
            booster[t] = true;
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                p[j] = max(p[j], p[t] - w[i]);
            }
        }
        hh++;
    }
}

方案二用dfs递归遍历所有放不放放大器的情况，并适时剪枝。遍历所有情况用一个数组来记录是否放放大器，每次要分为放和不放两种情况，再接着调用递归函数。每次递归要遍历是否存在压力小于Pmin的情况，如果存在且在当前数组所在点之前出现小于的情况直接return（剪枝操作），如果是之后则继续递归。如果出现递归中此种情况统计的放大器个数大于之前的直接return（剪枝操作），或者统计完所有节点直接return。如果遍历中没有出现小于Pmin的情况则跟新放大器个数为当前统计和之前统计中较小的那个。

void dfs(int index, int cnt){
    int t = q[index];
    if (index >= n - 1){
        ans = min(ans, cnt);
        return;
    }
    int flag = 0;
    //判断当前点连接的所有点的压力值是否有小于最小压力值的
    for (int i = h[t]; i != -1; i = ne[i]) {
        int j = e[i];
        int tempp = p[t] - w[i];
        if (tempp < Pmin){
            flag = 1;
            break;
        }
     }
    //左分支：不放
    if (flag == 0) {
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            p[j] = max(p[j], p[t] - w[i]);
        }
        dfs(index + 1, cnt);
    }
    //右分支：放（第二次进循环）
    if (flag == 1) {
        cnt++;
        //剪枝
        if (cnt >= ans)
            return;
        else {
            p[t] = Pmax;
            booster[t] = true;
            for (int i = h[t]; i != -1; i = ne[i])
            {
                int j = e[i];
                p[j] = max(p[j], p[t] - w[i]);
            }
            dfs(index + 1, cnt);
        }
    }
}

主函数中用函数得到计数器、以及系统时钟频率来计算时间的值，并将其baocunda哦文件中，并用一段代码将这些结果整理为markdown图标文件。

int main(){
    memset(h, -1, sizeof h);
    cin >> Pmax >> Pmin;
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int x, y, c;//起点、终点、距离
        cin >> x >> y >> c;
        add(x, y, c);
        d[y]++;//入度
    }
    for (int i = 1; i <= n; i++){
        p[i] = -0x3f3f3f3f;
        booster[i] = false;
    }
    p[1] = Pmax;
    if (topsort(d)) {
        cout << "拓扑排序成功\n";
    }
    else {
        cout << "拓扑排序不成功\n";
    }
    cout << "拓扑序为";
    for (int i = 0; i < n; i++){
        cout << q[i] << " ";
    }
    cout << endl;
    //方案1
    LARGE_INTEGER litmp1, litmp2;//用于存储系统时钟频率和初始计数值
    long long qt1, qt2;
    double dft, dff, dfm;
    QueryPerformanceFrequency(&litmp1);//获取系统时钟的频率，并将结果存储在 litmp1 变量中
    dff = (double)litmp1.QuadPart;//将 litmp1 中的时钟频率值转换为 double 类型，并将其赋值给变量 dff。
    QueryPerformanceCounter(&litmp1);//获取当前系统的计数值（初始值），并将结果存储在 litmp1 变量中
    qt1 = litmp1.QuadPart;//初始计数值
    bfs();
    cout << "方案一放大器的放置位置；";
    for (int i = 1; i <= n; i++) {
        if (booster[i]) cout << i << " ";
    }
    cout << endl;
    cout << "方案一得出的最少放大器个数为：" << ans << endl;
    QueryPerformanceCounter(&litmp1);//获得终止值
    qt2 = litmp1.QuadPart;//终止计数值
    dfm = (double)(qt2 - qt1);
    dft = dfm / dff;//获得对应的时间值
    ofstream fout1;
    fout1.open("scheme1time.txt", ios::app);//将方案一的时间值存入文件中
    fout1 << dft << endl;
    fout1.close();
    //方案2
    topsort(d);
    for (int i = 1; i <= n; i++){
        p[i] = -0x3f3f3f3f;
        booster[i] = false;
    }
    p[1] = Pmax;
    ans = INT_MAX;
    QueryPerformanceFrequency(&litmp2);//获得时钟频率
    dff = (double)litmp2.QuadPart;
    QueryPerformanceCounter(&litmp2);//获得初始值
    qt1 = litmp2.QuadPart;
    dfs(0, 0);
    cout << "方案二放大器的放置位置；";
    for (int i = 1; i <= n; i++){
        if (booster[i]) cout << i << " ";
    }
    cout << endl;
    cout << "方案二得出的最少放大器个数为：" << ans << endl;
    QueryPerformanceCounter(&litmp2);//获得终止值
    qt2 = litmp2.QuadPart;
    dfm = (double)(qt2 - qt1);
    dft = dfm / dff;//获得对应的时间值
    ofstream fout2;
    fout2.open("scheme2time.txt", ios::app);
    fout2 << dft << endl;
    fout2.close();
    return 0;
}

#include <iostream>
#include <fstream>
#include<vector>
using namespace std;
vector<double> a, b;

void read(vector<double>& array, string path){
    ifstream fin;
    fin.open(path);
    double temp;
    while (fin >> temp){
        array.push_back(temp);
    }
    fin.close();
}
int main(){
    read(a, "scheme1time.txt");
    read(b, "scheme2time.txt");
    ofstream fout("time.md");
    fout << "|scheme|example1|example2|example3|example4|" << endl;
    fout << "|--|--|--|--|--|" << endl;
    fout << "|1|" << a[0] << "|" << a[1] << "|" << a[2] << "|" << a[3] << "|" << endl;
    fout << "|2|" << b[0] << "|" << b[1] << "|" << b[2] << "|" << b[3] << "|" << endl;
    return 0;
}

测试结果（以及提供样例）

样例一和终端输出

其他三个样例

样例二

51 2
8 12
1 2 50
1 3 40
1 6 43
2 5 41
2 6 22
2 4 1
4 6 11
5 6 9
5 7 32
7 8 35
7 8 23
6 8 7

样例三

30 3
16 21
1 2 28
1 3 25
1 4 5
2 7 9
2 6 15
3 5 10
4 5 20
4 6 30
5 7 10
5 8 26
6 9 7
7 13 23
8 10 5
8 11 1
9 12 10
9 14 9
11 12 2
10 13 6
13 16 4
11 16 19
14 15 13

样例四

94 3
15 90
1 2 59
1 3 33
1 12 58
1 10 6
1 2 48
1 9 68
1 10 28
1 2 67
1 9 83
1 5 64
1 6 67
1 10 39
2 4 13
2 5 5
2 10 48
2 9 85
2 8 29
2 14 49
2 6 32
2 15 76
3 11 49
3 5 41
3 15 67
3 14 92
3 10 77
3 5 19
3 5 32
4 6 21
4 15 28
4 5 52
4 8 92
4 13 53
4 7 5
4 5 87
5 11 78
5 12 76
5 13 43
5 14 2
5 7 26
5 13 89
5 6 90
5 14 58
5 7 77
5 14 52
5 12 17
5 12 40
5 11 14
5 11 66
5 6 29
5 6 27
5 6 88
6 7 10
6 13 65
6 13 88
6 7 38
6 9 65
6 7 33
6 14 67
7 8 31
7 9 55
7 9 62
7 10 90
7 15 85
7 9 71
7 10 50
8 13 88
8 15 94
8 12 84
8 12 17
8 15 59
9 10 41
9 10 68
9 13 26
9 12 29
9 15 25
9 15 40
9 13 13
9 12 16
10 12 22
10 13 16
10 12 47
10 15 32
10 12 47
11 12 2
12 15 94
12 13 57
12 13 59
12 13 26
13 14 84
14 15 45

两种方法的时间统计和表格

完整代码和做图标代码

统计时间的代码

#include<iostream>
#include<vector>
#include<fstream>
#include<string>
#include<queue>
#include<windows.h>
using namespace std;
typedef pair<int, int> pp;
const int N = 1000010;
int Pmax, Pmin;
int h[N];//i是结点编号，值是以i为起点第一条边的编号
int e[N];//i是边编号，值是i这条边终点的结点编号
int ne[N];//值是和i这条边同起点的下一条边的编号
int w[N];
int p[N];//点i的压力值
bool booster[N];//点i是否放放大器
int idx;
int d[N];//存储每个点的入度
int q[N];//存储拓扑序列
int st[N];//记录是否遍历过的状态
int dis[N];//距离
vector<pp> path;//记录最小生成树路径
int n, m;//边数、点数
int ans;//结果
void add(int a, int b, int c){
    e[idx] = b;//终点
    w[idx] = c;//减少的值
    ne[idx] = h[a];//同起点的其他点
    h[a] = idx++;
}
//拓扑排序
bool topsort(int di[]){
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++){
        if (di[i]==0) q[++tt] = i;
    }
    while (hh <= tt){
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if (--di[j] == 0) q[++tt] = j;
        }
    }
    return tt == n - 1;
}
void bfs(){//贪心
    int hh = 0;
    while (hh <= n - 1){
        //按拓扑序列遍历
        int t = q[hh];
        int flag = 0;
        int minp;
        //检查当前节点是否要放放大器
        for (int i = h[t]; i != -1; i = ne[i]){//遍历与当前节点邻接的点
            int j = e[i];
            minp = p[t] - w[i];
            //最小值检查是否需要放
            if (minp < Pmin){
                flag = 1;
                break;
            }
        }
        //所有与当前节点连接的结点的压力值更新
        if (flag == 0) {
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                p[j] = max(p[j], p[t] - w[i]);
            }
        }
        if (flag == 1) {
            ans++;
            p[t] = Pmax;
            booster[t] = true;
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                p[j] = max(p[j], p[t] - w[i]);
            }
        }
        hh++;
    }
}
void dfs(int index, int cnt){
    int t = q[index];
    if (index >= n - 1){
        ans = min(ans, cnt);
        return;
    }
    int flag = 0;
    //判断当前点连接的所有点的压力值是否有小于最小压力值的
    for (int i = h[t]; i != -1; i = ne[i]) {
        int j = e[i];
        int tempp = p[t] - w[i];
        if (tempp < Pmin){
            flag = 1;
            break;
        }
     }
    //左分支：不放
    if (flag == 0) {
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            p[j] = max(p[j], p[t] - w[i]);
        }
        dfs(index + 1, cnt);
    }
    //右分支：放（第二次进循环）
    if (flag == 1) {
        cnt++;
        //剪枝
        if (cnt >= ans)
            return;
        else {
            p[t] = Pmax;
            booster[t] = true;
            for (int i = h[t]; i != -1; i = ne[i])
            {
                int j = e[i];
                p[j] = max(p[j], p[t] - w[i]);
            }
            dfs(index + 1, cnt);
        }
    }
}
int main(){
    memset(h, -1, sizeof h);
    cin >> Pmax >> Pmin;
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int x, y, c;//起点、终点、距离
        cin >> x >> y >> c;
        add(x, y, c);
        d[y]++;//入度
    }
    for (int i = 1; i <= n; i++){
        p[i] = -0x3f3f3f3f;
        booster[i] = false;
    }
    p[1] = Pmax;
    if (topsort(d)) {
        cout << "拓扑排序成功\n";
    }
    else {
        cout << "拓扑排序不成功\n";
    }
    cout << "拓扑序为";
    for (int i = 0; i < n; i++){
        cout << q[i] << " ";
    }
    cout << endl;
    //方案1
    LARGE_INTEGER litmp1, litmp2;//用于存储系统时钟频率和初始计数值
    long long qt1, qt2;
    double dft, dff, dfm;
    QueryPerformanceFrequency(&litmp1);//获取系统时钟的频率，并将结果存储在 litmp1 变量中
    dff = (double)litmp1.QuadPart;//将 litmp1 中的时钟频率值转换为 double 类型，并将其赋值给变量 dff。
    QueryPerformanceCounter(&litmp1);//获取当前系统的计数值（初始值），并将结果存储在 litmp1 变量中
    qt1 = litmp1.QuadPart;//初始计数值
    bfs();
    cout << "方案一放大器的放置位置；";
    for (int i = 1; i <= n; i++) {
        if (booster[i]) cout << i << " ";
    }
    cout << endl;
    cout << "方案一得出的最少放大器个数为：" << ans << endl;
    QueryPerformanceCounter(&litmp1);//获得终止值
    qt2 = litmp1.QuadPart;//终止计数值
    dfm = (double)(qt2 - qt1);
    dft = dfm / dff;//获得对应的时间值
    ofstream fout1;
    fout1.open("scheme1time.txt", ios::app);//将方案一的时间值存入文件中
    fout1 << dft << endl;
    fout1.close();
    //方案2
    topsort(d);
    for (int i = 1; i <= n; i++){
        p[i] = -0x3f3f3f3f;
        booster[i] = false;
    }
    p[1] = Pmax;
    ans = INT_MAX;
    QueryPerformanceFrequency(&litmp2);//获得时钟频率
    dff = (double)litmp2.QuadPart;
    QueryPerformanceCounter(&litmp2);//获得初始值
    qt1 = litmp2.QuadPart;
    dfs(0, 0);
    cout << "方案二放大器的放置位置；";
    for (int i = 1; i <= n; i++){
        if (booster[i]) cout << i << " ";
    }
    cout << endl;
    cout << "方案二得出的最少放大器个数为：" << ans << endl;
    QueryPerformanceCounter(&litmp2);//获得终止值
    qt2 = litmp2.QuadPart;
    dfm = (double)(qt2 - qt1);
    dft = dfm / dff;//获得对应的时间值
    ofstream fout2;
    fout2.open("scheme2time.txt", ios::app);
    fout2 << dft << endl;
    fout2.close();
    return 0;
}

做图标的代码

#include <iostream>
#include <fstream>
#include<vector>
using namespace std;
vector<double> a, b;

void read(vector<double>& array, string path){
    ifstream fin;
    fin.open(path);
    double temp;
    while (fin >> temp){
        array.push_back(temp);
    }
    fin.close();
}
int main(){
    read(a, "scheme1time.txt");
    read(b, "scheme2time.txt");
    ofstream fout("time.md");
    fout << "|scheme|example1|example2|example3|example4|" << endl;
    fout << "|--|--|--|--|--|" << endl;
    fout << "|1|" << a[0] << "|" << a[1] << "|" << a[2] << "|" << a[3] << "|" << endl;
    fout << "|2|" << b[0] << "|" << b[1] << "|" << b[2] << "|" << b[3] << "|" << endl;
    return 0;
}

另一种做法代码参考

class graph{
public:
    int idx = 0;
    int tp[N];//拓扑序列
    int in1[N];//记录点y的入度
    int p[N];
    bool s[N];//是否有放大器
    int tpn = 0;
    int ansnum;
    int n, m, Pmax;//点，边，权
    bool vis[N];//判断是否经过过这个点
    bool flag = true;
    int tnum;
    bool judge1(int tnum);
    graph(int n, int m, int Pmax){
        this->n = n;
        this->m = m;
        this->Pmax = Pmax;
        idx = 0;
    }
    void add(int x, int y, int z);
    void tpsort();
    void dfs1(int ss, int num);
};
void graph::add(int x, int y, int z){
    e[idx] = y;
    w[idx] = z;
    ne[idx] = h[x];
    h[x] = idx++;
    in1[y] ++;
}
//生成拓扑序列
void graph::tpsort(){
    tpn = 0;
    queue<int> q;
    for (int i = 1; i <= n; i++){
        if (in1[i] == 0)
            q.push(i);
    }
    while (q.size()) {
        auto t = q.front();
        q.pop();
        tp[++tpn] = t;
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            in1[j] --;
            if (in1[j] == 0)
                q.push(j);
        }
    }
}
bool graph::judge1(int tnum){
    flag = true;
    s[1] = true;
    memset(vis, false, sizeof vis);
    vis[1] = true;
    for (int i = 1; i <= n; i++) p[i] = Pmax;
    for (int i = 1; i <= n; i++){
        int t = tp[i];
        if (p[t] < Pmin){
            if (i <= tnum) flag = false;
            return false;
        }
        if (s[t]) p[t] = Pmax;//如果放了放大器
        for (int j = h[t]; j != -1; j = ne[j]){
            int u = e[j];
            if (!vis[u]){//没到过
                p[u] = p[t] - w[j];
                vis[u] = true;
            }
            else p[u] = min(p[u], p[t] - w[j]);
        }
    }
    for (int i = 1; i <= n; i++){
        int t = tp[i];
        if (p[t] < Pmin){
            if (t <= tnum) flag = false;
            return false;
        }
    }
    return true;
}
void graph::dfs1(int ss, int num){
    if (ss > this->n + 1 || num > ansnum)
        return;
    else if (judge1(ss - 1)){//完整的一次遍历
        ansnum = min(ansnum, num);
        return;
    }
    else if (flag == false){
        return;
    }
    s[tp[ss]] = true;
    dfs1(ss + 1, num + 1);
    s[tp[ss]] = false;
    dfs1(ss + 1, num);
}

如能打赏，不胜感激[叩谢]。

标签：10,课程设计,12,15,int,13,数据结构,山东大学,Pmax
From： https://blog.csdn.net/Water_Star1/article/details/140375144

山东大学数据结构与算法课程设计实验4网络放大器设置问题

问题描述

基本要求

数据结构与算法描述

测试结果（以及提供样例）

样例一和终端输出

其他三个样例

样例二

样例三

样例四

两种方法的时间统计和表格

完整代码和做图标代码

统计时间的代码

做图标的代码

另一种做法代码参考

相关文章

赞助商

阅读排行

山东大学数据结构与算法课程设计实验4网络放大器设置问题

问题描述

基本要求

数据结构与算法描述

测试结果 （以及提供样例）

样例一和终端输出

其他三个样例

样例二

样例三

样例四

两种方法的时间统计和表格

完整代码和做图标代码

统计时间的代码

做图标的代码

另一种做法代码参考

相关文章

赞助商

阅读排行

测试结果（以及提供样例）