【BZOJ3732】Network,NOIP2013货车运输,ygylca
跟NOIP的题是一模一样的,我重写了一遍,这个代码更清晰一点。
思路见http://blog.csdn.net/vmurder/article/details/38734663
但我仍要再说一遍思路。
首先我们最小生成树建图,这个就不进行证明了,因为按照kruskal建图的话,每遍历过一条边,就相当于有一些询问间有了道路,而且一定是该边。
然后就是ygylca了。思想:把要处理的东西扔到该节点,按一定顺序在该节点处理,并且处理后扔到lca,然后因为到了lca处时有些需要顺序处理的信息已经处理完了,所以可以在这里处理像处理的信息。
比如本题就是两点到lca的路径中的最长边较大值。
这个树边类题思想的时间复杂度很优秀哦!而且思路远比树剖清晰,比较好写,但是只能离线,即使做在线也是用一些跟时间戳有关的方法将在线转换成离线做。
中间的TLE是另一种没深想的思想,可能可以优化,读者可以看看。
直接看代码,然后手模拟就好了。
#include <cstdio> #include <cstring> #include <algorithm> #define N 101000 using namespace std; struct KSD { int u,v,next,note,len; bool operator < (const KSD &a)const {return len<a.len;} }e[N],eq[N],elca[N],road[N]; int head[N],headq[N],headlca[N]; int cnt,cntq,cntlca; void add(int u,int v,int len) { ++cnt; e[cnt].u=u; e[cnt].v=v; e[cnt].len=len; e[cnt].next=head[u]; head[u]=cnt; } void addq(int u,int v) { ++cntq; eq[cntq].u=u; eq[cntq].v=v; eq[cntq].next=headq[u]; headq[u]=cntq; } void addlca(int u,int v,int lca,int note) { ++cntlca; elca[cntlca].u=u; elca[cntlca].v=v; elca[cntlca].next=headlca[lca]; elca[cntlca].note=note; headlca[lca]=cntlca; } int n,m,p; int f[N],l[N],visit[N],vis[N],ans[N]; int find(int x) { int t=f[x]; if(f[x]==x)return x; f[x]=find(f[x]); l[x]=max(l[x],l[t]); return f[x]; } void ygylca(int x,int p,int len) { int i,u,v,fa,fb; for(i=head[x];i;i=e[i].next) { v=e[i].v; if(v==p)continue; ygylca(v,x,e[i].len); } for(i=headq[x];i;i=eq[i].next) { v=eq[i].v; if(visit[v])addlca(x,v,find(v),i+1>>1); } for(i=headlca[x];i;i=elca[i].next) { u=elca[i].u; v=elca[i].v; find(u); find(v); ans[elca[i].note]=max(l[u],l[v]); } visit[x]=vis[x]=1; l[x]=len; f[x]=p; } void Kruskal() { int i,j,k; int fa,fb; for(i=1;i<=n;i++)f[i]=i; for(i=1;i<=m;i++)scanf("%d%d%d",&road[i].u,&road[i].v,&road[i].len); sort(road+1,road+m+1); for(i=1;i<=m;i++) { fa=find(road[i].u); fb=find(road[i].v); if(fa!=fb) { f[fa]=fb; add(road[i].u,road[i].v,road[i].len); add(road[i].v,road[i].u,road[i].len); } } } int main() { // freopen("test.in","r",stdin); int i,j,k; int a,b,c; scanf("%d%d%d",&n,&m,&p); Kruskal(); memset(ans,-1,sizeof(ans)); for(i=1;i<=n;i++)f[i]=i; for(i=1;i<=p;i++) { scanf("%d%d",&a,&b); addq(a,b); addq(b,a); } for(i=1;i<=n;i++) { if(!vis[i]) { ygylca(i,0,0); memset(visit,0,sizeof(visit)); } } for(i=1;i<=p;i++)printf("%d\n",ans[i]); return 0; }
TLE做法(或可优化)
#include <cstdio> #include <cstring> #include <algorithm> #define N 20000 #define M 40000 #define Q 20000 using namespace std; struct KSD { int u,v,len; bool operator < (const KSD &a)const {return len<a.len;} }e[M]; struct Query { int u,v,ans,note; }query[Q],stk[2][Q]; int n,m,q,top[2]; int f[N]; int find(int x) { if(x==f[x])return x; return f[x]=find(f[x]); } int main() { // freopen("test.in","r",stdin); int i,j,k; int flag,len,now; int u,v; scanf("%d%d%d",&n,&m,&q); for(i=1;i<=n;i++)f[i]=i; for(i=1;i<=m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].len); for(i=1;i<=q;i++)scanf("%d%d",&query[i].u,&query[i].v),query[i].note=i; for(i=1;i<=q;i++)stk[0][i]=query[i]; top[0]=q;sort(e+1,e+m+1); for(now=0,flag=1;top[now]&&flag<=m;top[now]=0,now^=1) { for(len=e[flag].len;e[flag].len==len;flag++) { f[find(e[flag].v)]=find(e[flag].u); } for(i=1;i<=top[now];i++) { u=stk[now][i].u; v=stk[now][i].v; if(find(u)==find(v))query[stk[now][i].note].ans=len; else stk[now^1][++top[now^1]]=stk[now][i]; } } for(i=1;i<=q;i++)printf("%d\n",query[i].ans); return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。