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

非常暴力美学的线性规划。。。囧。。。不知为何，让我想起 SPOJ CAKE3。。。

值得注意的事。。。首先分数类是可以偷懒不写的…（暴力枚举分母）。。。
然后也没必要分 d[][] 和 w[][] 进行讨论，因为反正都相等了。。。
最后所有的约束关系恰好就是所有的三角不等式。。
（也就是 floyd 算法里的 kij、但这个题里因为反正都约束条件，所以你经典顺序写错的话也会不影响计算结果囧… ）。。。。

const int N = 10;
int d[N][N], x0[N][N], x1[N][N];
int n;

struct Simplex {
    const static int N = int(1e2) + 9, M = int(1e3) + 9;
    DB a[N][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];
        }
    }

    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);
        }
    }

    void gao() {

        if (RD(::n) == 2) {
            puts("0/1");
            return;
        }
        n = m = 0;

        REP(i, ::n) FOR(j, i+1, ::n) {
            x0[i][j] = x0[j][i] = ++n;
            x1[i][j] = x1[j][i] = ++n;
        }

// z b
// c A

        Rush {
            int x, y, w; RD(x, y, w);
            d[x][y] = d[y][x] = w;
            a[x0[x][y]][0] = a[x1[x][y]][0] = 1;
        }


        REP(k, ::n) REP(i, ::n) FOR(j, i+1, ::n) {
            // d[i][k] + d[k][j] <= d[i][j]
            ++m;
            a[0][m] += d[i][j] - d[i][k] - d[k][j];
            a[x0[i][j]][m] -= 1; a[x1[i][j]][m] += 1;
            a[x0[i][k]][m] += 1; a[x1[i][k]][m] -= 1;
            a[x0[k][j]][m] += 1; a[x1[k][j]][m] -= 1;
        }

        DB z = run();
        //printf("%.9f\n", z);
        int i = 1; while (sgn(z * i, int(z*i+0.5))) ++i;
        printf("%d/%d\n",int(z*i+0.5), i);
    }
} fst;

int main() {

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

Posted by xiaodao
Category: 日常