• https://www.luogu.com.cn/problem/P4043
• https://darkbzoj.cc/problem/3876
• https://blog.bill.moe/AHOI2014-plot/

const int N = int(5e3) + 9, M = int(3e2) + 9;

VI in[M], out[M];

struct Simplex {
    DB a[N+1][M+1];
    int n, m;

    void pivot(int in, int out) {
        REP(i, m+1) if(i!=in) a[out][i] /= -a[out][in]; //重置out约束
        a[out][in] = 1/a[out][in];

        REP(i, n+1) if (i!=out && sgn(a[i][in])) { //重新计算其他约束
            DB t = a[i][in]; a[i][in] = 0;
            REP(j, m+1) 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);
        }
    }

    int gao() {
        // z b
        // c A
        int n, m = 0; RD(n);

        REP_1(i, n) {
            Rush {
                int j; RD(j); a[0][0] += RD(a[++m][0]);
                out[i].PB(m); in[j].PB(m);
            }
        }

        FOR_1(i, 2, n) {
            a[0][i] += SZ(out[i]) - SZ(in[i]);
            for (auto j: in[i]) a[j][i] -= 1;
            for (auto j: out[i]) a[j][i] += 1;
        }
        this->n = m; this->m = n;
        return run();
    }
} fst;

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    OT(fst.gao());
}

Posted by xiaodao
Category: 日常