[DS记录]P4350 [CERC2015]Export Estimate

**题意** ； 给出一张 $n$ 个点 $m$ 条边的简单无向图，边有边权。 有 $q$ 次询问，每次询问给出一个阈值 $t$，问你把权值 $<t$ 的边删掉以后，执行下列操作，最终状态的点数与边数。 - 按编号从小到大考虑每个点，如果孤立点就删掉（操作一），如果度数为 $2$ 就把它简化成一条边（操作二）。（具体地，若 $u-t-v$ ，则简化为 $u-v$） 注意，可能产生自环或重边。 权值$,n,m,q\leq 3\times 10^5$ ，时限$\texttt{4s}$。 ------------ 将边按照权值从小到大排序（可以桶排序），增量维护。 - 考虑一个点 $u$ 何时会被删除 我们发现，操作不会影响剩余点的度数。 - 孤立点 - 度数为二的点 当且仅当操作完之后为自环， $u$ 才会保留，否则会被删除。 反向考虑，从一个自环逆着做操作二，观察能得到什么东西。答案是一个纯环。 因此，若连通分量不为纯环，则该点最终一定会被删除。 再考虑一个纯环会变成什么样，不难发现只剩下编号最大的点。 于是，当且仅当连通分量为纯环，且该点为编号最大的点，才不会被删除。 容易用并查集维护每个连通分量的二度点个数，以及是否为纯环（全为二度点）。 每个操作二恰好删 $2$ 条边加 $1$ 条边，也容易考虑。 复杂度 $O(n\alpha(n))$ 。 ```cpp #include<algorithm> #include<cstdio> #include<vector> #define MaxN 300500 using namespace std; int f[MaxN],c2[MaxN],c[MaxN]; int find(int u) {return f[u]==u ? u : f[u]=find(f[u]);} bool chk(int u,int v) {return find(u)==find(v);} void merge(int u,int v) { u=find(u);v=find(v); if (c[u]>c[v])swap(u,v); f[u]=v; c[v]+=c[u];c2[v]+=c2[u]; } int sump,d[MaxN]; void add(int u) { if (d[u]==0)sump++; if (d[u]==2)c2[find(u)]--; d[u]++; if (d[u]==2)c2[find(u)]++; } int calc(int u){ u=find(u); return c2[u]==c[u] ? c2[u]-1 : c2[u]; } struct Line{int u,v;}; vector<Line> l[MaxN]; int n,m,q,ans[MaxN],ans2[MaxN]; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++){f[i]=i;c[i]=1;} for (int i=1,u,v,w;i<=m;i++){ scanf("%d%d%d",&u,&v,&w); l[w].push_back((Line){u,v}); } int buf=0,suml=0; for (int i=300000;i>=0;i--){ for (int j=0;j<l[i].size();j++){ int u=l[i][j].u,v=l[i][j].v; if (chk(u,v)){ buf-=calc(u); add(u);add(v); buf+=calc(u); }else { buf-=calc(u)+calc(v); merge(u,v);add(u);add(v); buf+=calc(u); } }suml+=l[i].size(); ans[i]=sump-buf;ans2[i]=suml-buf; } scanf("%d",&q); for (int i=1,k;i<=q;i++){ scanf("%d",&k); printf("%d %d\n",ans[k],ans2[k]); }return 0; } ```