Imperial roads

· · 个人记录

2017-2018 ACM-ICPC Latin American Regional Programming Contest, problem: (I) Imperial roads

题目链接：Codeforces GYM 101889，Problem I。

题目大意

给定 n 点 m 边无向图，Q 次询问，每次询问必须给出一条图上边，要求必须包含这条边，并且选择任意其他边，构成连通子图，每条边有其边权，求其最小代价是多少。

数据范围：n,Q\leq 10^5，m\leq 2\times 10^5。

思路

显然，这是一个生成树问题。

类似于次小生成树，跑一个替换边操作，非常板子，没什么好说的。

kruskal 最小生成树时间复杂度：O(m\log m)；
求 LCA 并替换边时间复杂度：O(\log n)。

总时间复杂度：O(m\log m+Q\log n)，可过。

附：次小生成树。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
struct edge {
    int to,nx,wt;
} eg[N*4];
int hd[N],tot;
void adeg(int u,int v,int w) {
    eg[++tot]={v,hd[u],w};
    hd[u]=tot;
}
int fa[N];
int find(int u) {
    if(fa[u]==u) return u;
    return fa[u]=find(fa[u]);
}
void merge(int u,int v) {
    u=find(u),v=find(v);
    fa[u]=v;
}
vector<pair<pair<int,int>,int> > g;
bool cmp(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b){
    return a.second<b.second;
}
set<pair<int,int> > st;
map<pair<int,int>,int> mp;
ll kruskal(int n,int m) {
    ll res=0;
    sort(g.begin(),g.end(),cmp);
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=0;i<m;++i) {
        int u=g[i].first.first,v=g[i].first.second;
        int w=g[i].second;
        if(find(u)==find(v)) continue;
        adeg(u,v,w);
        adeg(v,u,w);
        st.insert(make_pair(u,v));
        st.insert(make_pair(v,u));
        res+=w;
        merge(u,v);
    } return res;
}
int f[N][20],dep[N],dis[N][20];
void dfs(int u,int fa) {
    f[u][0]=fa;
    dep[u]=dep[fa]+1;
    for(int i=1;i<20;++i)
        f[u][i]=f[f[u][i-1]][i-1],
        dis[u][i]=max(dis[u][i-1],dis[f[u][i-1]][i-1]);
    for(int i=hd[u];i;i=eg[i].nx) {
        int to=eg[i].to;
        if(to==fa) continue;
        dis[to][0]=eg[i].wt;
        dfs(to,u);
    }
}
int lca(int u,int v) {
    if(dep[u]<dep[v]) swap(u,v); //dep[u]>=dep[v]
    for(int i=19;i>=0;--i)
        if(dep[f[u][i]]>=dep[v])
            u=f[u][i];
    if(u==v) return u;
    for(int i=19;i>=0;--i)
        if(f[u][i]!=f[v][i])
            u=f[u][i],v=f[v][i];
    if(u==v) return u;
    return f[u][0];
}
int maxpath(int u,int fa) {
    int mx=0;
    for(int i=19;i>=0;--i)
        if(dep[f[u][i]]>=dep[fa])
            mx=max(dis[u][i],mx),
            u=f[u][i];
    return mx;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr),
    cout.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;++i) {
        int u,v,w;
        cin>>u>>v>>w;
        g.push_back({{u,v},w});
        mp.insert({{u,v},w});
        mp.insert({{v,u},w});
    }
    ll res=kruskal(n,m);
    dfs(1,0);
    int q;
    cin>>q;
    while(q--) {
        int u,v;
        cin>>u>>v;
        if(st.find(make_pair(u,v))!=st.end())
            cout<<res<<'\n';
        else {
            ll w=mp[make_pair(u,v)];
            int LCA=lca(u,v);
            ll zc=max(maxpath(u,LCA),maxpath(v,LCA));
            cout<<res-zc+w<<'\n';
        }
    }
    return 0;
}