1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
#pragma once
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
template <typename T>
class Matrix{
vector<vector<T>> mat; //list of rows
int W=0,H=0;
public:
template <typename U>
class RowAccess{
vector<T> &row;
public:
RowAccess(vector<T> &row):row(row){}
T& operator[](int x){return row[x];}
const T& operator[](int x) const {return row[x];}
T& front(){return row.front();}
const T& front() const {return row.front();}
T& back(){return row.back();}
const T& back() const {return row.back();}
};
template <typename U>
class ConstRowAccess{
const vector<T> &row;
public:
ConstRowAccess(const vector<T> &row):row(row){}
const T& operator[](int x) const {return row[x];}
const T& front() const {return row.front();}
const T& back() const {return row.back();}
};
Matrix() = default;
Matrix(int W,int H)
:W(W),H(H){
mat.resize(H);
for(auto &row : mat){
row.resize(W);
}
}
void addrow(){
mat.emplace_back(W,T());
H++;
}
void addcolumn(){
for(auto &row : mat){
row.emplace_back();
}
W++;
}
void resize(int w,int h){
if(h<H){
H=h;
mat.resize(H);
}
if(w!=W){
W=w;
for(auto &row : mat){
row.resize(w);
}
}
if(h>H){
mat.resize(h);
for(int i=H;i<h;i++){
mat[i].resize(W);
}
H=h;
}
}
void clear(){
mat.clear();
}
RowAccess<T> operator[](int y){
return RowAccess<T>(mat[y]);
}
ConstRowAccess<T> operator[](int y) const {
return ConstRowAccess<T>(mat[y]);
}
int width() const {return W;}
int height() const {return H;}
};
class Problem{
enum VarType{
VT_NORMAL=0,
VT_SLACK,
VT_ART,
};
vector<VarType> vartype;
vector<double> zfunc;
double zvalue=0;
Matrix<double> restr;
vector<double> bvec;
vector<int> basis;
void removefrombasis(int varidx);
void solve_noart();
public:
Problem(const Problem&) = default;
Problem(istream &in);
void solve();
double solutionValue() const;
vector<double> solutionVars() const;
friend istream& operator>>(istream &in,Problem &prob);
friend ostream& operator<<(ostream &os,const Problem &prob);
};
istream& operator>>(istream &in,Problem &prob);
ostream& operator<<(ostream &os,const Problem &prob);
|
