LOJ #3534. 「NOI2021」庆典
2022/7/20 23:25:20
本文主要是介绍LOJ #3534. 「NOI2021」庆典,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
提交记录
题目叙述
给定一个 \(n\) 个点 \(m\) 条边的有向图,满足如果 \(x\) 到 \(w\) 右边,并且 \(y\) 到 \(w\) 也有边,那么就一定有边 \(x\) 到 \(y\) 或者 \(y\) 到 \(x\) 。每次给出 \(k\) 条边 \(a_i\rightarrow b_i\) 表示这次询问新加入的边(不一定这样做之后的图还满足原题的限制)和点 \(s,t\) ,求所有 \(s\) 到 \(t\) 可能经过的节点数量。
题解
事实上那个条件,等价于缩点之后的图,有用的边严格构成一棵树。如果 \(x\rightarrow y\) ,\(y\rightarrow z\) ,\(x\rightarrow z\) ,那么我们称 \(x\rightarrow z\) 是无用的。这是因为如果要走到 \(z\) , \(x\rightarrow y\rightarrow z\) 肯定比 \(x\rightarrow z\) 走过的节点数量多。
然后考虑这个题怎么做。有一种暴力是不管那个树的性质,直接 \(s\) 开始搜一遍,\(t\) 开始在反图上搜一遍,如果一个点两次搜索都能到达,那么就是可以经过的。
怎么优化呢,直接对 \(s\) 和 \(t\) 还有新加入的两条边在树上的点建立虚树。有个人问如果经过不在虚树上的点怎么办,我说直接将那样的点的个数放到边权上就可以了。虚树上的父子关系,直接父亲向儿子连,边权为路径节点数量,然后跑暴力即可。
总结
- 从“什么样的节点可以经过”这样的角度,就是说答案贡献的角度考虑问题。
代码
一堆模板叠加。。。209行。
#include <cstdio> #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <set> #define pii pair<int,int> #define macro_expand(x) #x #define print_macro(x) printf("%s\n",macro_expand(x)) #define FOR(i,l,r) for(int i=(l),i##ADJK=(r);i<=i##ADJK;++i) #define ROF(i,r,l) for(int i=(r),i##ADJK=(l);i>=i##ADJK;--i) using namespace std; typedef long long LL; template<typename T>bool chkmax(T &x,const T y){return (x<y)?(x=y,1):0;} template<typename T>bool chkmin(T &x,const T y){return (x>y)?(x=y,1):0;} char In[1<<20],*Ss=In,*Tt=In; #define getchar() (Ss==Tt&&(Tt=(Ss=In)+fread(In,1,1<<20,stdin),Ss==Tt)?EOF:*Ss++) inline int read(){ int f=0,x=0; char ch=getchar(); while(!isdigit(ch)){f|=(ch=='-');ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return f?-x:x; } const int MN=3e5+5,MM=6e5+5; int N,M,Q,K; struct Edge1{ int v,nxt; Edge1():v(0),nxt(0){} Edge1(int _v,int _nxt):v(_v),nxt(_nxt){} }; template<const int TMN,const int TMM>struct Graph1{ int head[TMN]; Edge1 edge[TMM]; int tot; void clear(){tot=0,memset(head,0,sizeof(head));} void AddE(int u,int v){ edge[++tot]=Edge1(v,head[u]); head[u]=tot; } }; Graph1<MN,MM> G; Graph1<MN,MN> T; #define go(G,p,u) for(int p=G.head[u];p;p=G.edge[p].nxt) int dfn[MN],low[MN],dfstime; bool ins[MN]; int stk[MN],top,col[MN],totcol,siz[MN]; void tarjan(int u){ low[u]=dfn[u]=++dfstime; ins[u]=1; stk[++top]=u; go(G,p,u){ int v=G.edge[p].v; if(!dfn[v]){ tarjan(v); chkmin(low[u],low[v]); }else if(ins[v])chkmin(low[u],dfn[v]); } if(low[u]==dfn[u]){ int tmp=0; ++totcol; do{ tmp=stk[top]; ins[tmp]=0; // 忘了这句话。 col[tmp]=totcol; ++siz[totcol]; --top; }while(tmp!=u); } } set<pii> s; int dt,sum[MN]; int euler[MN*2],dep[MN],in[MN]; void dfs(int u,int ff){ sum[u]=sum[ff]+siz[u]; in[u]=++dt; euler[dt]=u; dep[u]=dep[ff]+1; go(T,p,u){ int v=T.edge[p].v; dfs(v,u); euler[++dt]=u; } } int min_val[MN*2][21],min_pos[MN*2][21],lg2[MN*2]; void init(){ FOR(i,1,dt)min_val[i][0]=dep[euler[i]],min_pos[i][0]=i; // dep[euler[i]]!!! FOR(i,2,dt)lg2[i]=lg2[i>>1]+1; FOR(i,1,19){ FOR(j,1,dt-(1<<i)+1){ if(min_val[j][i-1]>min_val[j+(1<<(i-1))][i-1]){ min_val[j][i]=min_val[j+(1<<(i-1))][i-1]; min_pos[j][i]=min_pos[j+(1<<(i-1))][i-1]; }else{ min_val[j][i]=min_val[j][i-1]; min_pos[j][i]=min_pos[j][i-1]; } } } } int lca(int u,int v){ int l=in[u],r=in[v],d=lg2[r-l+1]; if(l>r)swap(l,r); if(min_val[l][d]>min_val[r-(1<<d)+1][d])return euler[min_pos[r-(1<<d)+1][d]]; else return euler[min_pos[l][d]]; } int node[15],vtot,vfa[MN]; void build(int *id,int len){ sort(id+1,id+len+1,[](const int &x,const int &y){return in[x]<in[y];}); vtot=0; FOR(i,1,len){ node[++vtot]=id[i]; if(i!=len)node[++vtot]=lca(id[i],id[i+1]); } sort(node+1,node+vtot+1,[](const int &x,const int &y){return in[x]<in[y];}); vtot=unique(node+1,node+vtot+1)-node-1; // 这句话不能放在后面 FOR(i,1,vtot){ if(i==1)vfa[node[i]]=0; else vfa[node[i]]=lca(node[i-1],node[i]); } } Graph1<13,16> G2,G3; bool vis2[MN],vis3[MN]; bool debug_tag; void dfs2(const Graph1<13,16> &G,bool *vis,int u){ vis[u]=1; go(G,p,u){ int v=G.edge[p].v; // 开始忘记判断这件事情了。 if(!vis[v]) dfs2(G,vis,v); } } int get(int v){return lower_bound(node+1,node+vtot+1,v)-node;} Graph1<MN,MM> G4; int dis[MN],fa[MN]; int main(){ freopen("celebration.in","r",stdin); freopen("celebration.out","w",stdout); N=read(),M=read(),Q=read(),K=read(); FOR(i,1,M){ int u=read(),v=read(); G.AddE(u,v); } FOR(i,1,N)if(!dfn[i])tarjan(i); FOR(u,1,N){ go(G,p,u){ int v=G.edge[p].v; if(col[u]!=col[v]){ G4.AddE(col[u],col[v]); fa[col[v]]=col[u]; } } } ROF(u,totcol,1){ go(G4,p,u){ int v=G4.edge[p].v; if(chkmax(dis[v],dis[u]+1)) fa[v]=u; } } ROF(i,totcol,1){ if(fa[i])T.AddE(fa[i],i); dep[i]=dep[fa[i]]+1; } dfs(totcol,0); init(); while(Q--){ G2.clear(),G3.clear(); int s=0,t=0; static int a[5],b[5]; s=read(),t=read(); FOR(i,1,K)a[i]=read(),b[i]=read(); static int nd[15],tot; tot=0; nd[++tot]=col[s],nd[++tot]=col[t]; FOR(i,1,K)nd[++tot]=col[a[i]],nd[++tot]=col[b[i]]; sort(nd+1,nd+tot+1); tot=unique(nd+1,nd+tot+1)-nd-1; build(nd,tot); sort(node+1,node+vtot+1); FOR(i,1,vtot){ if(vfa[node[i]]){ int u=get(vfa[node[i]]),v=get(node[i]); G2.AddE(u,v); G3.AddE(v,u); } } FOR(i,1,K){ G2.AddE(get(col[a[i]]),get(col[b[i]])); G3.AddE(get(col[b[i]]),get(col[a[i]])); } FOR(i,1,vtot)vis2[i]=vis3[i]=0; dfs2(G2,vis2,get(col[s])); // col[s] debug_tag=1; dfs2(G3,vis3,get(col[t])); debug_tag=0; int ans=0; FOR(i,1,vtot)if(vis2[i]&&vis3[i])ans+=siz[node[i]]; FOR(i,1,vtot)if(vfa[node[i]]){ int x=get(node[i]),y=get(vfa[node[i]]); if(vis2[x]&&vis3[x]&&vis2[y]&&vis3[y])ans+=sum[node[i]]-sum[vfa[node[i]]]-siz[node[i]]; } printf("%d\n",ans); } fclose(stdin); fclose(stdout); return 0; }
这篇关于LOJ #3534. 「NOI2021」庆典的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?