• https://darkbzoj.cc/problem/3118
• https://blog.bill.moe/bzoj3118-MST/

小心重边。

const int N = 300 + 9, M = int(1e3) + 9;

struct Tree {
    VI adj[N]; int fa[N], dep[N];

    void dfs(int u = 1, int p = -1) {
        for (auto v: adj[u]) if (v != p) {
            fa[v] = u; dep[v] = dep[u] + 1;
            dfs(v, u);
        }
    }
} T;

struct Graph {
    int id[N][N];

    struct edge {
        int x, y, w, inT, c;
        void in(int i) {
            int a, b; RD(x, y, w, inT, a, b);
            c = inT ? b : a;
        }
    } E[M];

    int n, m;

    void in() {
        RD(n, m); REP_1(i, m) {
            E[i].in(i);
            if (E[i].inT) {
                int x = E[i].x, y = E[i].y;
                T.adj[x].PB(y); T.adj[y].PB(x);
                id[x][y] = id[y][x] = i;
            }
        }
        T.dfs();
    }
} G;


struct Simplex {
    const static int N = ::M, M = int(1e4) + 9;
    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]; //重置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);
        }
    }

    int gao() {

        // z b
        // c A

        G.in();
        n = G.m; m = 0; REP_1(i, n) {
            a[i][0] = G.E[i].c;
            int u = G.E[i].x, v = G.E[i].y;
            if (T.dep[u] < T.dep[v]) swap(u, v);
            if (!G.E[i].inT) { // E[i] is not a tree edge
                while (u != v) {
                    int p = T.fa[u];
                    int j = G.id[p][u]; // E[j] is a tree edge
                    if (G.E[i].w < G.E[j].w) {
                        ++m; a[i][m] = a[j][m] = -1;
                        a[0][m] = G.E[j].w - G.E[i].w;
                    }
                    u = p; if (T.dep[u] < T.dep[v]) swap(u, v);
                }
            }
        }

        return run();
    }
} fst;


int main() {

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

Posted by xiaodao
Category: 日常