资料

• https://oi-wiki.org/math/simplex/
• https://blog.bill.moe/simplex-algorithm-notes/
• https://notes.sshwy.name/Math/Linear-Algbra/LP-and-its-Dual/
• https://www.zybuluo.com/winee/note/1186606
• https://en.wikipedia.org/wiki/Simplex_algorithm
• https://en.wikipedia.org/wiki/Ellipsoid_method
• https://en.wikipedia.org/wiki/Interior-point_method
• https://www.codechef.com/viewsolution/7183029
• https://github.com/kth-competitive-programming/kactl/blob/f6a97d9e5766c90ee71a97a90cd3faf6cff0ca72/content/numerical/Simplex.h

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

「ONTAK2010」Vacation

「ZJOI2013」防守战线

[NOI2008] 志愿者招募

• Luogu P3980. [NOI2008] 志愿者招募
• BZOJ #3265. 志愿者招募加强版

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矩阵m行n列
        n = _n+1; m = _m+1;
    }
    void pivot(int in, int out) {
        REP(i, m) if(i!=in) a[out][i] /= -a[out][in]; //重置out约束
        a[out][in] = 1/a[out][in];

        REP(i, n) if (i!=out && sgn(a[i][in])) { //重新计算其他约束
            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

    // z D
    // C A

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

Posted by xiaodao
Category: 日常