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;
}