Original link: https://www.shuizilong.com/house/archives/luogu-p4043-ahoi2014-jsoi2014%E6%94%AF%E7%BA%BF%E5%89%A7%E6%83%85/
- 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]; //reset out constraint a[out][in] = 1/a [out][in]; REP(i, n+1) if (i!=out && sgn(a[i][in])) { //Recalculate other constraints 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() { // zb // 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()); }
This article is reproduced from: https://www.shuizilong.com/house/archives/luogu-p4043-ahoi2014-jsoi2014%E6%94%AF%E7%BA%BF%E5%89%A7%E6%83%85/
This site is for inclusion only, and the copyright belongs to the original author.