There is No Alternative

· · 个人记录

Codeforces GYM 100803, Problem F, There is No Alternative

题目大意

给定一张 n 点 m 边的图，求最小生成树中不可被替代的边。

数据范围：n\leq 500，m\leq \min\{n(n-1)/2,\ 5\times 10^4\}。

思路

这个题的数据范围确实弱了一点，我觉得 n\leq 5000 也是可做的。

进行 n 次次小生成树替换，如果可以换掉那么说明不是不可替代的边。

比较水，一遍过。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct node {
    int to,nx,wt,id;
} eg[N];
int hd[N],tot;
void adeg(int u,int v,int w,int id) {
    eg[++tot]={v,hd[u],w,id};
    hd[u]=tot;
}
struct edge {
    int u,v,w;
    bool operator < (const edge a) { return w<a.w; }
};
struct DSU {
    int fa[N];
    void init(int n) { for(int i=1;i<=n;++i) fa[i]=i; }
    int find(int u) { return ((fa[u]==u)?(u):(fa[u]=find(fa[u]))); }
    void merge(int u,int v) { fa[find(u)]=find(v); }
} d;
vector<edge> e;
bitset<N> ingr,rpl;
int kruskal(int n) {
    d.init(n); int res=0;
    for(int i=0;i<e.size();++i) {
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if(d.find(u)==d.find(v)) continue;
        ingr[i]=true;
        d.merge(u,v);res+=w;
        adeg(u,v,w,i),adeg(v,u,w,i);
    } return res;
}
vector<int> es;
int f[N][20],dep[N];
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];
    for(int i=hd[u];i;i=eg[i].nx) {
        int to=eg[i].to;
        if(to==fa) continue;
        dfs(to,u);
    }
}
int LCA(int u,int v) {
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=19;i>=0;--i)
        if(dep[f[u][i]]>=dep[v]) u=f[u][i];
    for(int i=19;i>=0;--i)
        if(f[u][i]==f[v][i]);
        else u=f[u][i],v=f[v][i];
    if(u==v) return u;
    return f[u][0];
}
void findpath(int u,int ed) {
    if(u==ed) return;
    for(int i=hd[u];i;i=eg[i].nx) {
        if(eg[i].to!=f[u][0]) continue;
        es.push_back(eg[i].id);
        findpath(f[u][0],ed);
    }
}
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;
        e.push_back({u,v,w});
    } sort(e.begin(),e.end());
    int sz=kruskal(n);
    dfs(1,0);
    for(int i=0;i<m;++i) {
        if(ingr[i]) continue;
        int lca=LCA(e[i].u,e[i].v);
        es.clear();
        findpath(e[i].u,lca);
        findpath(e[i].v,lca);
        for(auto c:es)
            if(e[c].w>=e[i].w)
                rpl[i]=true,rpl[c]=true;
    } int res1=0;
    long long res2=0;
    for(int i=0;i<m;++i)
        if(ingr[i]&&!rpl[i]) res1++,res2+=e[i].w;
    cout<<res1<<' '<<res2<<'\n';
    return 0;
}