LCA问题,看了一天关于LCA问题,包括在线算法和离线算法,感冒发烧头疼,反正是看的挺难受的,
其中包括在线算法,即 LCA转化为RMQ模型,还有离线算法,即tarjan,终于下定耐着性子把tarjan写完了,中间各种细节,想想都头疼,还好AC了,不然真没劲改下去了
code:
#include <cstring> #include <cstdio> using namespace std; const int MAXN = 20010 ; struct node { int to,next; int dis; // dis 在tree中表示权 ,在query中表示编号 }Edges[MAXN],Querys[2000010]; int vis[MAXN],ans[2000010]; int n,father[MAXN],dis[MAXN]; int e_cnt,q_cnt,eadj[MAXN],qadj[MAXN]; void init() { int i; for(i=1;i<=n;i++) father[i]=i; e_cnt=q_cnt=1; memset(eadj,0,sizeof(eadj)); memset(qadj,0,sizeof(qadj)); memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); } void addEdge(int a,int b,int dis) { Edges[e_cnt].to=b; Edges[e_cnt].dis=dis; Edges[e_cnt].next=eadj[a]; eadj[a]=e_cnt++; } void addQuery(int a,int b,int id) { Querys[q_cnt].to=b; Querys[q_cnt].dis=id; Querys[q_cnt].next=qadj[a]; qadj[a]=q_cnt++; } int find(int x) { if(x!=father[x]) father[x] = find(father[x]); return father[x]; } void merge(int x,int y) { x=find(x); y=find(y); if(x==y) return ; if(y<x) father[x]=y; else father[y]=x; } void tarjan(int u,int dist,int root) { dis[u]=dist; vis[u]=root; father[u]=u; int i,to; for(i=eadj[u];i;i=Edges[i].next) { to=Edges[i].to; if(!vis[to]) { tarjan(to,dist+Edges[i].dis,root); father[to]=u; } } for(i=qadj[u];i;i=Querys[i].next) { to=Querys[i].to; if(vis[to]) { if(vis[to]!=root) ans[Querys[i].dis] = -1; else ans[Querys[i].dis] = dis[to] + dis[u] - 2 * dis[find(to)]; } } } int main() { int i,j,m,q,a,b,c; while (~scanf("%d%d%d",&n,&m,&q)) { init(); for (i = 1; i <= m; ++i) { scanf("%d%d%d",&a,&b,&c); addEdge(a,b,c); addEdge(b,a,c); } for (i = 1; i <= q; ++i) { scanf("%d%d",&a,&b); addQuery(a,b,i); addQuery(b,a,i); } for (i = 1; i <= n; ++i) if (!vis[i]) tarjan(i,0,i); //以i为根遍历整棵树 for (i = 1; i <= q; ++i) if (ans[i] != -1) printf("%d\n",ans[i]); else printf("Not connected\n"); } return 0; }