LG7737 [NOI2021]庆典
2022/1/16 23:07:21
本文主要是介绍LG7737 [NOI2021]庆典,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
[NOI2021] 庆典
前言
调了 2 天才过掉。。。
仔细想想,整个思考过程还是很有借鉴意义的。
解题思路
我们拿到的是一个有意思图,我们考虑一步一步将图转化。最好处理的图类型是什么?是树,我们能否把原图转化为在叶向树上的问题呢?
step 1
我们容易想到将一个有向图通过缩点转化为 DAG。我们跑一遍 tarjan 就可以了。
容易证明,缩点后的 DAG 还满足原图所满足的那个奇怪的条件。
step 2
我们现在有了一个 DAG,可以拓扑排序了。这有什么用呢?我们回顾题目中有一个奇怪的条件:
若 \(x\Rightarrow z\) 且 \(y\Rightarrow z\),那么有 \(x\Rightarrow y\) 或 \(y\Rightarrow x\)。
假设有 \(x\Rightarrow y\),也就是说,如果我们现在通过 \(x\) 有一条直接的边可以到达 \(z\),且 \(y\) 可以到达 \(z\)。我们排序肯定先排 \(x\) 后 \(y\),最后 \(z\)。我们可以考虑删掉 \(x\Rightarrow z\) 这条边,因为,这对答案没有任何影响。由此我们可以得到一颗叶向树。
step 3
我们现在得到了一颗树,已经可以暴力了,但是时间复杂度太高了,由于 \(k\) 很小,我们考虑建造虚树。
我们对 \(s,t\) 和每条边涉及的点建造虚树(注意可能有重复,要去重)。虚树的边权为这个边上出两个端点有多少个点。我们再把临时边加到虚树里,边权为 \(0\),顺手建个反向图。让 \(s,t\) 双向奔赴一下,计算出有多少边点可以被同时遍历到即可。
代码
本题难点之一可能在于如何清空虚树和如何理清每个图之间的关系,理解了后就很简单了。
(代码又长又臭)
//Don't act like a loser. //This code is written by huayucaiji //You can only use the code for studying or finding mistakes //Or,you'll be punished by Sakyamuni!!! #include<bits/stdc++.h> using namespace std; int read() { char ch=getchar(); int f=1,x=0; while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return f*x; } char read_char() { char ch=getchar(); while(!isalpha(ch)) { ch=getchar(); } return ch; } const int MAXN=3e5+10; int n,m,q,k,rt,tms,tot,top,colcnt,ans; int ind[MAXN],f[MAXN][21],lst[15],mrk[15],dfn[MAXN],stk[MAXN],val[MAXN],sum[MAXN],cal[MAXN],dep[MAXN],dis[MAXN]; int low[MAXN],col[MAXN],sz[MAXN],bel[MAXN]; bool vis[MAXN]; stack<int> s; struct edge { int u,v,id,nxt; }; struct graph { edge e[MAXN<<2]; int cnt,h[MAXN]; void addedge(int u,int v,int w) { e[++cnt].v=v; e[cnt].id=w; e[cnt].nxt=h[u]; h[u]=cnt; } }g0,g1,g2; struct small_graph { edge e[500]; int cnt,h[MAXN]; bool vis[MAXN]; void addedge(int u,int v,int w) { e[++cnt].v=v; e[cnt].id=w; e[cnt].u=u; e[cnt].nxt=h[u]; h[u]=cnt; } void dfs(int u) { cal[u]++; if(cal[u]==2) { ans+=sz[u]; } vis[u]=1; for(int i=h[u];i;i=e[i].nxt) { sum[e[i].id]++; if(!vis[e[i].v]) dfs(e[i].v); } } void clear() { for(int i=1;i<=cnt;i++) { h[e[i].u]=0; cal[e[i].u]=0; cal[e[i].v]=0; vis[e[i].u]=0; vis[e[i].v]=0; e[i]=e[0]; } cnt=0; } }g3,g4; bool cmp(int a,int b) { return dfn[a]<dfn[b]; } void get(int x,int y) { if(dis[y]<dis[x]) { swap(x,y); } val[++tot]=dis[y]-dis[x]-sz[y]; } void tarjan(int u) { dfn[u]=low[u]=++tms; vis[u]=1; s.push(u); for(int i=g0.h[u];i;i=g0.e[i].nxt) { int v=g0.e[i].v; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(vis[v]){ low[u]=min(low[u],dfn[v]); } } if(dfn[u]==low[u]) { colcnt++; while(!s.empty()&&low[s.top()]==dfn[u]) { int v=s.top(); s.pop(); vis[v]=0; col[v]=colcnt; sz[colcnt]++; bel[v]=colcnt; } } } void topo() { queue<int> q; for(int i=1;i<=colcnt;i++) { if(!ind[i]) { q.push(i); rt=i; } } while(!q.empty()) { int u=q.front(); q.pop(); for(int i=g1.h[u];i;i=g1.e[i].nxt) { int v=g1.e[i].v; ind[v]--; if(!ind[v]) { g2.addedge(u,v,0); q.push(v); } } } } void dfs(int u,int fa) { f[u][0]=fa; dep[u]=dep[fa]+1; dis[u]=dis[fa]+sz[u]; dfn[u]=++tms; for(int i=g2.h[u];i;i=g2.e[i].nxt) { int v=g2.e[i].v; if(v!=fa) { dfs(v,u); } } } void lca_init() { for(int i=1;i<=20;i++) { for(int j=1;j<=n;j++) { f[j][i]=f[f[j][i-1]][i-1]; } } } int LCA(int u,int v) { if(dep[u]<dep[v]) { swap(u,v); } for(int i=20;i>=0;i--) { if(dep[f[u][i]]>=dep[v]) { u=f[u][i]; } } if(u==v) { return u; } for(int i=20;i>=0;i--) { if(f[u][i]!=f[v][i]) { u=f[u][i]; v=f[v][i]; } } return f[u][0]; } void build(int n) { sort(lst+1,lst+n+1,cmp); stk[++top]=lst[1]; for(int i=2;i<=n;i++) { int p=lst[i]; int lca=LCA(lst[i],stk[top]); while(1) { if(dep[lca]<=dep[stk[top]]&&dep[lca]>=dep[stk[top-1]]) { if(lca==stk[top]) { ; } else if(lca==stk[top-1]) { get(stk[top-1],stk[top]); g3.addedge(stk[top-1],stk[top],tot); g4.addedge(stk[top],stk[top-1],tot); top--; } else { get(lca,stk[top]); g3.addedge(lca,stk[top],tot); g4.addedge(stk[top],lca,tot); stk[top]=lca; } break; } else { get(stk[top-1],stk[top]); g3.addedge(stk[top-1],stk[top],tot); g4.addedge(stk[top],stk[top-1],tot); top--; } } stk[++top]=lst[i]; } for(int i=1;i<top;i++) { get(stk[i+1],stk[i]); g3.addedge(stk[i],stk[i+1],tot); g4.addedge(stk[i+1],stk[i],tot); } for(int i=1;i<=k;i++) { g3.addedge(mrk[i*2-1],mrk[i*2],0); g4.addedge(mrk[i*2],mrk[i*2-1],0); } } void clear1() { for(int i=1;i<=n;i++) { dfn[i]=ind[i]=low[i]=0; } tms=0; } void clear2(int n) { for(int i=0;i<=tot;i++) { sum[i]=0; val[i]=0; } top=tot=ans=0; g3.clear(); g4.clear(); for(int i=1;i<=n;i++) { cal[lst[i]]=0; g3.vis[lst[i]]=0; g4.vis[lst[i]]=0; g3.h[lst[i]]=0; g4.h[lst[i]]=0; } } int main() { freopen("temp.in","r",stdin); //freopen("temp.out","w",stdout); cin>>n>>m>>q>>k; for(int i=1;i<=m;i++) { int u,v; u=read(),v=read(); ind[v]++; g0.addedge(u,v,0); } for(int i=1;i<=n;i++) { if(!dfn[i]) { tarjan(i); } } clear1(); for(int u=1;u<=n;u++) { for(int i=g0.h[u];i;i=g0.e[i].nxt) { int v=g0.e[i].v; if(bel[u]!=bel[v]) { g1.addedge(bel[u],bel[v],0); ind[bel[v]]++; } } } topo(); dfs(rt,0); lca_init(); for(int i=1;i<=q;i++) { int s,t; s=bel[read()];t=bel[read()]; for(int j=1;j<=k;j++) { lst[j*2-1]=mrk[j*2-1]=bel[read()]; lst[j*2]=mrk[j*2]=bel[read()]; } lst[k*2+1]=s; lst[k*2+2]=t; int nm=k*2+2; sort(lst+1,lst+nm+1); nm=unique(lst+1,lst+nm+1)-lst-1; build(nm); g3.dfs(s); g4.dfs(t); for(int j=1;j<=tot;j++) { ans+=(sum[j]==2? 1:0)*val[j]; } printf("%d\n",ans); clear2(nm); } //fclose(stdin); //fclose(stdout); return 0; } /* 5 6 3 0 5 2 3 5 3 2 2 4 2 5 3 1 3 2 4 5 4 3 */
这篇关于LG7737 [NOI2021]庆典的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)