【CF891C】Envy 离线+最小生成树
生成 最小 离线
2023-09-11 14:15:24 时间
【CF891C】Envy
题意:给你一个图,边有边权,每次询问给你一堆边,问你是否存在一个原图的最小生成树包含给出的所有边。
n,m,q<=100000
题解:思路很好的题。
首先有一个非常重要的性质,我们每次询问的边中,权值不同的边互不影响。(需要好好想一想,理解一下)
那么满足要求的MST存在当且仅当:对于询问中所有权值相同的边,都存在一个MST同时包含这些边。这又等价于什么?如果我们先把权值小于该权值的所有边先加入到图中求出MST,再把询问的边加入到图中,不能形成环。
于是做法自然就出来了。先离线,将每个询问拆成权值相同的若干个询问,在处理一个询问之前,将权值<询问的边的权值的 所有边都加入到图中求MST。然后处理这个询问,我们将每个连通块看成一个点,然后在连通块之间连边,再用dfs判环即可。最后将这些边删除。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <vector> using namespace std; const int maxn=500010; struct node { int a,b; node() {} node(int x,int y) {a=x,b=y;} }; int n,m,mx,Q,tot,cnt,flag; int ans[maxn],vis[maxn],bel[maxn],to[maxn<<1],nxt[maxn<<1],head[maxn],ins[maxn],f[maxn],pc[maxn],pa[maxn],pb[maxn]; vector<node> p[maxn],v[maxn]; vector<int> q[maxn]; vector<node>::iterator vi; vector<int>::iterator ii; int find(int x) { return (f[x]==x)?x:(f[x]=find(f[x])); } inline void add(int a,int b) { to[cnt]=b,nxt[cnt]=head[a],head[a]=cnt++; to[cnt]=a,nxt[cnt]=head[b],head[b]=cnt++; } void dfs(int x,int fa) { vis[x]=ins[x]=1; for(int i=head[x];!flag&&i!=-1;i=nxt[i]) if(i!=(fa^1)) { if(!vis[to[i]]) dfs(to[i],i); else if(ins[to[i]]) flag=1; } ins[x]=0; } inline int rd() { int ret=0,f=1; char gc=getchar(); while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar(); return ret*f; } int main() { n=rd(),m=rd(); int i,j,a,b,c; memset(head,-1,sizeof(head)); for(i=1;i<=m;i++) a=pa[i]=rd(),b=pb[i]=rd(),c=pc[i]=rd(),p[c].push_back(node(a,b)),mx=max(mx,c); Q=rd(); for(i=1;i<=Q;i++) { a=rd(); for(j=1;j<=a;j++) { b=rd(); if(vis[pc[b]]!=i) vis[pc[b]]=i,bel[pc[b]]=++tot,v[pc[b]].push_back(node(tot,i)); q[bel[pc[b]]].push_back(b); } } for(i=1;i<=n;i++) f[i]=i; for(i=1;i<=mx;i++) { for(vi=v[i].begin();vi!=v[i].end();vi++) { j=(*vi).a,cnt=0; for(ii=q[j].begin();ii!=q[j].end();ii++) add(a=find(pa[*ii]),b=find(pb[*ii])),vis[a]=vis[b]=0; flag=0; for(ii=q[j].begin();ii!=q[j].end()&&!flag;ii++) { if(!vis[a=find(pa[*ii])]) dfs(a,-1); if(!vis[b=find(pb[*ii])]) dfs(b,-1); } ans[(*vi).b]|=flag; for(ii=q[j].begin();ii!=q[j].end();ii++) head[find(pa[*ii])]=-1,head[find(pb[*ii])]=-1; } for(vi=p[i].begin();vi!=p[i].end();vi++) { a=find((*vi).a),b=find((*vi).b); if(a!=b) f[a]=b; } } for(i=1;i<=Q;i++) { if(ans[i]) puts("NO"); else puts("YES"); } return 0; }
相关文章
- Poj 3522 最长边与最短边差值最小的生成树
- 最好用的数据库文档生成工具
- 【CF891C】Envy(最小生成树)
- 【CF125E】MST Company(凸优化,最小生成树)
- 最小生成树之Kruskal算法和Prim算法
- 【BZOJ4144】[AMPPZ2014]Petrol 最短路+离线+最小生成树
- 【BZOJ1937】[Shoi2004]Mst 最小生成树 KM算法(线性规划)
- 【BZOJ3714】[PA2014]Kuglarz 最小生成树
- 图的最小生成树:Prim算法--解锁一批边,解锁一批节点
- POJ 3723 Conscription (最小生成树)
- UVa 1151 Buy or Build (最小生成树+二进制法暴力求解)
- 手动生成/etc/shadow文件中的密码
- 使用 Python 从图像生成 3D 网格,将深度学习与 3D 数据处理相结合以生成网格(基于 Open3D和 transformers)
- 《程序设计解题策略》——1.2 利用最小生成树及其扩展形式解题
- 用Python+ChatGPT批量生成论文概述
- Java实现生成数据库表结构文档(生成工具screw的使用)
- 支付宝 二维码/转账码/生成方式,突破二维码生成数量的限制
- 使用HTML5画布(canvas)生成阴影效果
- poj 1789 Truck History (最小生成树)
- python自动生成useragent
- 【bzoj3943】[Usaco2015 Feb]SuperBull 最小生成树
- Prim算法---最小生成树
- A - 还是畅通工程(最小生成树)