沙田镇网站建设公司,做的网站提示磁盘空间不足,wordpress 卡顿,有没有免费的资源可以在线观看LCA 题意#xff1a;LCA模板题#xff0c;输入n和m#xff0c;表示n个点m条边#xff0c;下面m行是边的信息#xff0c;两端点和权#xff0c;后面的那个字母无视掉#xff0c;没用的。接着k#xff0c;下面k个询问lca#xff0c;输出即可 有人说要考虑不连通的情况LCA模板题输入n和m表示n个点m条边下面m行是边的信息两端点和权后面的那个字母无视掉没用的。接着k下面k个询问lca输出即可 有人说要考虑不连通的情况我没考虑AC了另外可能有uu这样的询问不过这不影响照样是写模板没有特判一样能过 还是Tarjan快一些 LCA转RMQ在线算法 #include iostream
#include cstdio
#include cstring
#include cmath
using namespace std;
#define N 40010
#define M 25int tot;
int __pow[M];
int head[N];
struct edge{int u,v,w,next;
}e[2*N];
int ver[2*N],R[2*N],first[N],dir[N];
int dp[2*N][25];
bool vis[N];inline void add(int u , int v ,int w ,int k)
{e[k].u u; e[k].v v; e[k].w w;e[k].next head[u]; head[u] k;u u^v; v u^v; u u^v;e[k].u u; e[k].v v; e[k].w w;e[k].next head[u]; head[u] k;
}void dfs(int u ,int dep)
{vis[u] true; first[u] tot; ver[tot] u; R[tot] dep;for(int khead[u]; k!-1; ke[k].next)if( !vis[e[k].v] ){int v e[k].v , w e[k].w;dir[v] dir[u] w;dfs(v,dep1);ver[tot] u; R[tot] dep;}
}void ST(int len)
{int K (int)(log((double)(len)) / log(2.0));for(int i1; ilen; i) dp[i][0] i;for(int j1; jK; j)for(int i1; i__pow[j]-1 len; i){int a dp[i][j-1] , b dp[i__pow[j-1]][j-1];if(R[a] R[b]) dp[i][j] a;else dp[i][j] b;}
}int RMQ(int x ,int y)
{int K (int)(log((double)(y-x1)) / log(2.0));int a dp[x][K] , b dp[y-__pow[K]1][K];if(R[a] R[b]) return a;else return b;
}int LCA(int u ,int v)
{int x first[u] , y first[v];if(x y) swap(x,y);int index RMQ(x,y);return ver[index];
}int main()
{for(int i0; iM; i) __pow[i] (1i);int n,m,k,str[10];while(scanf(%d%d,n,m)!EOF){k 0;memset(head,-1,sizeof(head));memset(vis,false,sizeof(vis));while(m--){int u,v,w;scanf(%d%d%d%s,u,v,w,str);add(u,v,w,k);}tot dir[1] 0;dfs(1,1);ST(tot);int q;scanf(%d,q);while(q--){int u,v,lca;scanf(%d%d,u,v);lca LCA(u,v);printf(%d\n,dir[u] dir[v] - 2*dir[lca]);}}return 0;
} Tarjan离线算法 #include iostream
#include cstdio
#include cstring
using namespace std;
#define N 40010
#define M 20010int head[N];
struct edge{int u,v,w,next;
}e[2*N];
int __head[N];
struct ask{int u,v,lca,next;
}ea[M];
int fa[N],ance[N],dir[N];
bool vis[N];inline void add_edge(int u ,int v ,int w ,int k)
{e[k].u u; e[k].v v; e[k].w w;e[k].next head[u]; head[u] k;u u^v; v u^v; u u^v;e[k].u u; e[k].v v; e[k].w w;e[k].next head[u]; head[u] k;
}inline void add_ask(int u ,int v ,int k)
{ea[k].u u; ea[k].v v; ea[k].lca -1;ea[k].next __head[u]; __head[u] k;u u^v; v u^v; u u^v;ea[k].u u; ea[k].v v; ea[k].lca -1;ea[k].next __head[u]; __head[u] k;
}int find(int x){return x fa[x] ? x : fa[x] find(fa[x]);
}void Tarjan(int u)
{vis[u] true;ance[u] fa[u] u;for(int khead[u]; k!-1; ke[k].next)if( !vis[e[k].v] ){int v e[k].v , w e[k].w;dir[v] dir[u] w;Tarjan(v);fa[v] u;}for(int k__head[u]; k!-1; kea[k].next)if( vis[ea[k].v] )ea[k].lca ea[k^1].lca ance[find(ea[k].v)];
}int main()
{int n,m,q,k; char str[10];while(scanf(%d%d,n,m)!EOF){memset(head,-1,sizeof(head));memset(__head,-1,sizeof(__head));memset(vis,false,sizeof(vis));k 0;while(m--){int u,v,w;scanf(%d%d%d%s,u,v,w,str);add_edge(u,v,w,k);}scanf(%d,q);k 0;for(int i0; iq; i){int u ,v;scanf(%d%d,u,v);add_ask(u,v,k);}dir[1] 0;Tarjan(1);for(int i0; iq; i){int s i*2 , u ea[s].u , v ea[s].v , lca ea[s].lca;printf(%d\n,dir[u] dir[v] - 2*dir[lca]);}}return 0;
} 转载于:https://www.cnblogs.com/scau20110726/archive/2013/05/27/3102068.html
