求助站外题(单纯形法)
  • 板块学术版
  • 楼主ryanright
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/8/18 16:28
  • 上次更新2023/11/3 02:52:54
查看原帖
求助站外题(单纯形法)
182234
ryanright楼主2023/8/18 16:28

rt,原题链接。还没有判无解的情形,但是挂了 sub2,这些数据点的答案都小于 0。有没有大佬帮忙看看出了什么问题?

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
long double mat[105][105], c[105], b[105], z[105], ret[105];
bool vis[105];
int t[105];
int main() {
    int n, m, mode;
    cin >> n >> m >> mode;
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++)
            cin >> mat[i][j];
        mat[i][i + n] = 1;
        cin >> b[i];
    }
    for (int i = 1; i <= m; i++)
        t[i] = n + i;
    while (true) {
        int posi, posj;
        long double maxx = -1e20;
        for (int i = 1; i <= n + m; i++) {
            z[i] = c[i];
            for (int j = 1; j <= m; j++)
                z[i] -= c[t[j]] * mat[j][i];
            if (z[i] > maxx) {
                maxx = z[i];
                posj = i;
            }
        }
        if (maxx <= 0)
            break;
        long double minn = 1e20;
        for (int i = 1; i <= m; i++)
            if (mat[i][posj] > 0 && b[i] / mat[i][posj] < minn) {
                posi = i;
                minn = b[i] / mat[i][posj];
            }
        if (minn > 1e19) {
            cout << "Unbounded\n";
            return 0;
        }
        for (int i = 1; i <= n + m; i++)
            if (i != posj)
                mat[posi][i] /= mat[posi][posj];
        b[posi] /= mat[posi][posj];
        mat[posi][posj] = 1;
        for (int i = 1; i <= m; i++)
            if (i != posi) {
                for (int j = 1; j <= n + m; j++)
                    if (j != posj)
                        mat[i][j] -= mat[i][posj] * mat[posi][j];
                b[i] -= mat[i][posj] * b[posi];
                mat[i][posj] = 0;
            }
        t[posi] = posj;
    }
    long double ans = 0;
    for (int i = 1; i <= m; i++) {
        ans += b[i] * c[t[i]];
        ret[t[i]] = b[i];
        vis[t[i]] = true;
    }
    cout << fixed << setprecision(15) << ans << endl;
    if (mode)
        for (int i = 1; i <= n; i++)
            cout << fixed << setprecision(15) << ret[i] << ' ';
    return 0;
}
2023/8/18 16:28
加载中...