• https://www.codechef.com/submit/CHEFBOOK

我靠这个还要构造解。。。。
WA ing

const int N = 1000, M = N*N;
VI in[N], out[N];

struct Simplex {
    const static int N = int(1e4) + 9, M = int(1e4) + 9;
    DB a[N][M]; int b[N], c[M], X[M];
    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];
        }
        swap(c[in], b[out]);
    }

    void run() {

        REP_1(i, n) b[i] = -i;
        REP_1(i, m) c[i] = i;

        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;
            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) return; //throw ; //unbounded
            pivot(in, out);
        }
    }

    struct Edge {
        int x,y,w,s,t;
        void in() {
            RD(x,y,w,s,t);
            --x; --y;
        }
    } E[::M];

    void gao() {
// z c
// b A

        RD(n, m);

        REP(i, n) {
            in[i].clear();
            out[i].clear();
        }

        REP(i, m){
            E[i].in();
            int x = E[i].x, y = E[i].y, w = E[i].w, s = E[i].s, t = E[i].t;
            in[x].PB(y); out[y].PB(x); a[0][0] += w;
            DB (&r0)[M] = a[i+1]; r0[0] = t - w; r0[x+1] -= 1; r0[n+y+1] += 1;
            DB (&r1)[M] = a[m+i+1]; r1[0] = w - s; r1[x+1] += 1; r1[n+y+1] -= 1;
        }

        REP(i, n) a[0][i+1] += SZ(out[i]);
        REP(i, n) a[0][n+i+1] -= SZ(in[i]);

        n *= 2; m *= 2; swap(n, m);

        /*
        REP(i, n+1) {
            REP(j, m+1) cout << a[i][j] << " ";
            cout << endl;
        }

        REP_1(i, n) cout << b[i] << " "; cout << endl;
        REP_1(i, m) cout << c[i] << " "; cout << endl;
        REP_1(i, m) cout << X[i] << " "; cout << endl;
        */

        run();

        /*
        cout << "-----------" << endl;

        REP(i, n+1) {
            REP(j, m+1) cout << a[i][j] << " ";
            cout << endl;
        }
        cout << "-----------" << endl;
        */



        /*REP_1(i, m/2) {
            cout << a[0][i] << " "<< a[0][m/2+i] << endl;
        }*/


        REP_1(i, m) X[i] = 0;
        REP_1(i, n) if (b[i] > 0) X[b[i]] = a[i][0];

        /*
        REP_1(i, n) cout << b[i] << " "; cout << endl;
        REP_1(i, m) cout << c[i] << " "; cout << endl;
        REP_1(i, m) cout << X[i] << " "; cout << endl;
        */

        REP(i, n/2) {
            int x = E[i].x, y = E[i].y, w = E[i].w, s = E[i].s, t = E[i].t;
            w += X[x+1]; w -= X[m/2+y+1];
            if (w < s || t < w) {
                puts("Unlike");
                REP(i, n+1) {
                    REP(j, m+1) a[i][j] = 0;
                }
                return;
            }
        }

        OT((LL)a[0][0]);
        REP_1(i, m/2) {
            cout << (LL)X[i] << " "<< (LL)X[m/2+i] << endl;
        }


        REP(i, n+1) {
            REP(j, m+1) a[i][j] = 0;
        }
    }
} fst;

int main() {

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

Posted by xiaodao
Category: 日常