July 7, 2022
Codechef JUNE15. Chefbook

https://www.codechef.com/submit/CHEFBOOK
我靠这个还要构造解。。。。
WA ing
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
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: 日常
某岛

Codechef JUNE15. Chefbook

Archives

Blogroll

Links

Myself

Project
