emmm

Problem

给 $n$ 个点的图
求出 MST
给 $Q$ 个独立的询问
对于连接 $u,v$ 的边，将其边权更改（保证变大）
询问更改之后 MST 的大小
输出询问的平均值

Solution

先 Prim 跑 MST
然后如果更改一条边不属于 MST，则不变
如果属于，则相当于这条边被断开，需要找一条替代边
这条替代边肯定和这个边形成环
这条替代边肯定是尽量小的边
因此我们找出 MST 之后，枚举没在 MST 里的边，对于环上的边更新每条边的最佳替代边
到这里你就可以打树剖了
但我分析了一下复杂度和常数和码量还是放弃了（滚去翻题解）

如果我们对于没在 MST 里的边从小到大枚举
就不用树剖了，染色就行了
所以我们用一个并查集，如果某条边染了色，与它的父亲合并
这样的话每条边只会被染一次了

为了方便处理，我们还需要求下 LCA
就酱复杂度好像就成了 $O(m\log m + m\log n + n\log n + Q)$

以及请输出 4 位小数而不是五位。

Code

// Code by ajcxsu
// Problem: Genghis Khan the Conqueror

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T> void gn(T &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=3001, M=3001*3001;
struct Edge { int u, v, w; } ed[M];
bool cmp(const Edge &a, const Edge &b) { return a.w<b.w; }
int e[N][N];
int n, m;

int dist[N], fa[N];
bool S[N];
double prim() {
    memset(dist, 0x3f, sizeof(dist)), memset(fa, 0, sizeof(fa)), memset(S, 0, sizeof(S));
    dist[1]=0;
    int u=1, ma=0x3f3f3f3f;
    double ret=0;
    for(int i=1;i<=n;i++) {
        ma=0x3f3f3f3f;
        for(int j=1;j<=n;j++)
            if(!S[j] && dist[j]<ma) ma=dist[j], u=j;
        S[u]=1, ret+=dist[u];
        for(int j=1;j<=n;j++)
            if(!S[j] && dist[j]>e[u][j]) dist[j]=e[u][j], fa[j]=u;
    }
    return ret;
}

int dep[N], ff[N], W[N];
int dfs(int x) {
    if(dep[x]) return dep[x];
    if(!fa[x]) return dep[x]=1;
    return dep[x]=dfs(fa[x])+1;
}
const int OP=15;
int gup[N][OP];
void ini() {
    memset(gup, 0, sizeof(gup));
    for(int i=1;i<=n;i++) gup[i][0]=fa[i];
    for(int j=1;j<OP;j++)
        for(int i=1;i<=n;i++)
            gup[i][j]=gup[gup[i][j-1]][j-1];
    memset(ff, 0, sizeof(ff)), memset(W, 0x3f, sizeof(W));
}
int lca(int s, int t) {
    if(dep[s]<dep[t]) swap(s, t);
    for(int j=OP-1;j>=0;j--)
        if(dep[gup[s][j]]>=dep[t]) s=gup[s][j];
    if(s!=t) {
        for(int j=OP-1;j>=0;j--)
            if(gup[s][j]!=gup[t][j]) s=gup[s][j], t=gup[t][j];
        s=gup[s][0];
    }
    return dep[s];
}

int Find(int x) { return ff[x]?ff[x]=Find(ff[x]):x; }
bool Union(int a, int b) {
    int af=Find(a), bf=Find(b);
    if(af==bf) return false;
    ff[af]=bf;
    return true;
}

void paint(int x, int k, int w) {
    x=Find(x);
    while(dep[x]>k) {
        W[x]=w;
        Union(x, fa[x]);
        x=Find(x);
    }
}

int main() {
    double tot, rans;
    while(gn(n), gn(m), n) {
        memset(e, 0x3f, sizeof(e));
        int u, v, w;
        for(int i=1;i<=m;i++) {
            gn(u), gn(v), gn(w);
            u++, v++;
            e[u][v]=e[v][u]=min(e[u][v], w);
            ed[i]={u, v, w};
        }
        tot=prim(), rans=0;
        memset(dep, 0, sizeof(dep)), ini();
        for(int i=1;i<=n;i++) dfs(i);
        sort(ed+1, ed+1+m, cmp);
        for(int i=1;i<=m;i++) {
            if(dep[ed[i].u]<dep[ed[i].v]) swap(ed[i].u, ed[i].v);
            if(fa[ed[i].u]!=ed[i].v) {
                int l=lca(ed[i].u, ed[i].v);
                paint(ed[i].u, l, ed[i].w);
                paint(ed[i].v, l, ed[i].w);
            }
        }
        int q, rq;
        gn(q), rq=q;
        while(q--) {
            gn(u), gn(v), gn(w);
            u++, v++;
            if(dep[u]<dep[v]) swap(u, v);
            if(fa[u]==v)
                rans+=tot-dist[u]+min(w, W[u]);
            else rans+=tot;
        }
        rans/=rq;
        printf("%.4lf\n", rans);
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-uva-1504.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆