Brief description:

。。略）。。。

Analysis:

。。读题压力巨大。。。。但几乎就是裸的次小生成树。
。。不过是搞出 s[][] 之后用 checkMax 取代 checkMin。。。另外题目里说和 0 号结点相连的边保证不会发生故障。特判一下。。。。
（。。。这都能写不出实在是感人肺腑！。。）

const int N = 1009, M = N * 2;

DB w[N][N], _s[N][N], s[N][N]; bool inMST[N][N];
int hd[N], suc[M], to[M];
int n, m; DB mst;

void add_edgee(int a, int b){
    suc[m] = hd[a], to[m] = b, hd[a] = m++;
    suc[m] = hd[b], to[m] = a, hd[b] = m++;
    inMST[a][b] = inMST[b][a] = 1;
    _s[a][b] = _s[b][a] = OO;
}

void Prim(){
    static DB d[N]; static int c[N], pre[N]; RST(c); fill(d, d+n, OO); d[0] = 0; mst = 0, m = 2; DO(n){
        int u = 0; while (c[u]) ++u; FOR(i, u+1, n) if (!c[i] && d[i] < d[u]) u = i;
        if (u) add_edgee(pre[u], u); mst += d[u], c[u] = 1; REP(v, n) if (!c[v] && d[v] > w[u][v]) d[v] = w[u][v], pre[v] = u;
    }
}

#define v to[i]
int sta[N], top;

void dfs(int r, int u, int p){
    REP_G(i, u) if (v != p){
        dfs(r, v, u); checkMin(_s[r][u], _s[r][v]);
    }
}

void dfs(int u, int p){
    int t = top; sta[top++] = u; REP_G(i, u) if (v != p) dfs(v, u); if (!u) return;
    FOR(i, t, top) checkMin(s[u][p], _s[sta[i]][p]); s[p][u] = s[u][p];
}


int x[N], y[N];

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out2.txt", "w", stdout);
#endif

    Rush{
        int k; RD(n, k); RST(hd, inMST); REP(i, n) RD(x[i], y[i]);
        REP_2(i, j, n, n) w[i][j] = (i == j ? OO : dist((DB)(x[i]-x[j]), (DB)(y[i]-y[j]))), s[i][j] = OO;
        CPY(_s, w); Prim(); REP(i, n) dfs(i, i, i); top = 0, dfs(0, 0);
        DB res = 0; int i; FOR_N(i, 1, n) if (!inMST[0][i]) break;
        if (i != n) FOR(i, 1, n) FOR(j, i+1, n) if (inMST[i][j]) checkMax(res, s[i][j] - w[i][j]);
        OT((res+mst)*k);
    }
}

External link:

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1570178

Posted by xiaodao
Category: 日常