Luogu P4043. [AHOI2014/JSOI2014] Side Story

Original link: https://www.shuizilong.com/house/archives/luogu-p4043-ahoi2014-jsoi2014%E6%94%AF%E7%BA%BF%E5%89%A7%E6%83%85/

blank.jpg

   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.

Leave a Comment