Original link: https://www.shuizilong.com/house/archives/%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92/
material
exercise
ASC 2. Roads
- https://codeforces.com/gym/100197
- https://www.luogu.com.cn/problem/P4412
- https://darkbzoj.cc/problem/1937
- https://darkbzoj.cc/problem/3118
[NOI2008] Volunteer Recruitment
const int N = int(1e4) + 9, M = int(1e3) + 9; struct Simplex { DB a[N][M]; int n, m; void init(int _n,int _m) { //a matrix with m rows and n columns n = _n+1; m = _m+1; } void pivot(int in, int out) { REP(i, m) if(i!=in) a[out][i] /= -a[out][in]; //reset out constraint a[out][in] = 1/a[out ][in]; REP(i, n) if (i!=out && sgn(a[i][in])) { //Recalculate other constraints DB t = a[i][in]; a[i][in] = 0; REP(j, m) a[i][j] += t*a[out][j]; } } DB run() { while (true) { int in=0, out=0; DB Min=OO; REP_1(i, m) if(sgn(a[0][i])>0) { in=i; break; } if(!in)return a[0][0]; REP_1(i, n) if(sgn(a[i][in])<0&&a[i][0]/-a[i][in]<Min) { Min=a[i][0]/-a[i][in]; out=i; } if(!out)throw ; //unbounded pivot(in, out); } } } fst; int main() { #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif // zD // CA int n, m; RD(m, n); fst.init(n, m); REP_1(j, m) RD(fst.a[0][j]); REP_1(i, n) { int l, r; RD(l, r, fst.a[i][0]); FOR_1(j, l, r) fst.a[i][j]=-1; } printf("%d\n", int(fst.run())); }
This article is reproduced from: https://www.shuizilong.com/house/archives/%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92/
This site is for inclusion only, and the copyright belongs to the original author.