• CF603E Pastoral Oddities


    CF603E Pastoral Oddities

    给定一张 n" role="presentation" style="position: relative;">n 个点的无向图,初始没有边。

    依次加入 m" role="presentation" style="position: relative;">m 条带权的边,每次加入后询问是否存在一个边集,满足每个点的度数均为奇数。

    若存在,则还需要最小化边集中的最大边权。

    n105,m3×105" role="presentation" style="position: relative;">n105,m3×105

    首先观察题目条件,发现 n" role="presentation" style="position: relative;">n 的大小必须要是偶数。

    接着容易发现其实如果两个连通块大小都是偶数,他们之间的边不用连接。

    这样一步步寻找可以将题目条件转化为:整张图的所有连通块大小都为偶数

    那么现在需要每次加入一条边,对这张图做最小生成树

    显然暴力做需要 LCT 珂姬,而在线基本上就是行不通,会想到将所有边离线下来处理

    那么按照边权从小到大枚举,观察答案发现随着加入更多的边,答案一定不会增大

    这里向下容易掉进一个二分的坑中,对每条边二分一个最靠前的、满足条件的时间点,加入这条边。但其实在查询一个二分值的时候可能会有 O(n)" role="presentation" style="position: relative;">O(n) 的复杂度,难以接受。

    看看从小到大枚举每条边时我们的操作:如果二分到一个可行的时间点,那这个时间点以后的所有位置都不再需要考虑,并在剩余的位置加入这条边,这样成功的次数不超过 m" role="presentation" style="position: relative;">m 次,为什么不直接从大到小枚举每个时间点,尝试加入新的边直到这个时间点满足条件?(如果不满足条件再往前的都不会满足条件)

    这样需要一个数据结构支持在时间区间加入一条边、单点查询。这不就是线段树分治吗?

    那在线段树分治中先右再左递归询问,如果到达了一个叶子节点就尝试加入新的边,直到这个时间点满足条件。

    其中有个细节就是加入一条边的时候可能会加到自己这个节点上,那就添加的时候添加到 [l,r)" role="presentation" style="position: relative;">[l,r) 的位置,将当前时间轴跳过即可。

    1. #define Maxn 100005
    2. #define Maxm 300005
    3. int n,m,tp,Left,used,nowans;
    4. int fa[Maxn],siz[Maxn],ans[Maxm];
    5. pa sta[Maxm];
    6. struct EDGE
    7. {
    8. int l,r,u,v,val;
    9. EDGE(int L=0,int R=-1,int U=0,int V=0,int Val=0):
    10. l(L),r(R),u(U),v(V),val(Val){}
    11. inline friend bool operator < (EDGE x,EDGE y) { return x.val
    12. }e[Maxm];
    13. vector<int> tree[Maxm<<2];
    14. int Find(int x){ return (fa[x]==x)?x:Find(fa[x]); }
    15. inline void merge(int x,int y)
    16. {
    17. x=Find(x),y=Find(y);
    18. if(x==y) return;
    19. if(siz[x]>siz[y]) swap(x,y);
    20. Left-=(siz[x]&1)+(siz[y]&1);
    21. sta[++tp]=pa(x,y),fa[x]=y,siz[y]+=siz[x];
    22. Left+=siz[y]&1;
    23. }
    24. void addedge(int p,int nl,int nr,int l,int r,int x)
    25. {
    26. if(nl>=l && nr<=r) { tree[p].pb(x); return; }
    27. int mid=(nl+nr)>>1;
    28. if(mid>=l) addedge(p<<1,nl,mid,l,r,x);
    29. if(midaddedge(p<<1|1,mid+1,nr,l,r,x);
    30. }
    31. void solve(int p,int nl,int nr)
    32. {
    33. int Intp=tp,mid=(nl+nr)>>1;
    34. for(int i:tree[p]) merge(e[i].u,e[i].v);
    35. if(nl==nr)
    36. {
    37. for(;Left && used<=m;used++)
    38. {
    39. if(e[used].l>nl) continue;
    40. merge(e[used].u,e[used].v),nowans=e[used].val;
    41. if(e[used].laddedge(1,1,m,e[used].l,nl-1,used);
    42. }
    43. if(!Left) ans[nl]=nowans;
    44. else ans[nl]=-1;
    45. }
    46. else solve(p<<1|1,mid+1,nr),solve(p<<1,nl,mid);
    47. while(tp>Intp)
    48. {
    49. int x=sta[tp].fi,y=sta[tp].se;
    50. Left-=siz[y]&1,fa[x]=x,siz[y]-=siz[x];
    51. Left+=(siz[x]&1)+(siz[y]&1),tp--;
    52. }
    53. }
    54. int main()
    55. {
    56. Left=n=rd(),m=rd();
    57. for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
    58. for(int i=1,u,v,d;i<=m;i++)
    59. u=rd(),v=rd(),d=rd(),e[i]=EDGE(i,-1,u,v,d);
    60. sort(e+1,e+m+1),solve(1,1,m);
    61. for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    62. return 0;
    63. }
  • 相关阅读:
    Ajax详解
    132.【MySQL_进阶篇】
    Service详解
    操作系统题目收录(一)
    中移OneOS开发板学习入门
    【SpringBoot】之自动配置原理分析(源码级别)
    软件设计模式系列之八——适配器模式
    离散卡尔曼滤波实现
    C#多态浅析
    【深度学习】【Python】【Deepfashion2】 YOLOv5训练Deepfashion2数据集
  • 原文地址:https://blog.csdn.net/qq_53299575/article/details/126606782