公司网站建设攻略,公司做网站 手机 电脑,如何虚拟一个公司网站,wordpress中的全站链接怎么改正题
题目链接:https://www.luogu.com.cn/problem/P5236 题目大意
给一个边仙人掌#xff08;一条边至多在一个环中#xff09;#xff0c;每次询问两点之间的距离 解题思路
我们对于每个环新建方点#xff0c;然后方点连向所有环上的点#xff0c;然后计算一下每一条的…正题
题目链接:https://www.luogu.com.cn/problem/P5236 题目大意
给一个边仙人掌一条边至多在一个环中每次询问两点之间的距离 解题思路
我们对于每个环新建方点然后方点连向所有环上的点然后计算一下每一条的边权
需要注意的是如果两个询问点的LCALCALCA是一个方点那么需要特判 codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N3e410,K18;
struct node{int to,next,w;
}a[N*2],e[N*2];
int n,m,q,tot,num,cnt;
int f[N][K],s[N],val[N],dep[N],dis[N];
int ls[N],rs[N],dfn[N],low[N];
void addl(int x,int y,int w){a[tot].toy;a[tot].nextls[x];a[tot].ww;ls[x]tot;
}
void adde(int x,int y,int w){e[tot].toy;e[tot].nextrs[x];e[tot].ww;rs[x]tot;
}
void circle(int x,int y,int w){num;int nowy,sumw;while(now!f[x][0]){s[now]sum;sumval[now];nowf[now][0];}sums[num]s[x];s[x]0;nowy;int Dis;while(now!f[x][0]){Dismin(s[now],sum-s[now]);adde(num,now,Dis);adde(now,num,Dis);nowf[now][0];}return;
}
void tarjan(int x){dfn[x]low[x]cnt;int flag0;for(int ils[x];i;ia[i].next){int ya[i].to;if(yf[x][0])continue;if(!dfn[y]){f[y][0]x;val[y]a[i].w;tarjan(y);low[x]min(low[x],low[y]);}else low[x]min(low[x],dfn[y]);if(low[y]dfn[x])continue;adde(x,y,a[i].w);adde(y,x,a[i].w);}for(int ils[x];i;ia[i].next){int ya[i].to;if(xf[y][0]||dfn[x]dfn[y])continue;circle(x,y,a[i].w);}return;
}
void dfs(int x,int fa){for(int irs[x];i;ie[i].next){int ye[i].to;if(yfa)continue;dep[y]dep[x]1;dis[y]dis[x]e[i].w;f[y][0]x;dfs(y,x);}return;
}
int Get_dis(int x,int y){int ux,vy;if(dep[x]dep[y])swap(x,y);for(int iK-1;i0;i--)if(dep[f[y][i]]dep[x])yf[y][i];int lca;if(x!y){for(int iK-1;i0;i--)if(f[x][i]!f[y][i])xf[x][i],yf[y][i];lcaf[x][0];}else lcax;if(lcan)return dis[u]dis[v]-dis[lca]*2;else {int ansdis[u]-dis[x]dis[v]-dis[y];return ansmin(s[lca]-abs(s[x]-s[y]),abs(s[x]-s[y]));}
}
int main()
{scanf(%d%d%d,n,m,q);numn;for(int i1;im;i){int x,y,w;scanf(%d%d%d,x,y,w);addl(x,y,w);addl(y,x,w);}tot0;tarjan(1);dep[1]1;dfs(1,0);for(int i1;iK;i)for(int j1;jnum;j)f[j][i]f[f[j][i-1]][i-1]; for(int i1;iq;i){int x,y;scanf(%d%d,x,y);printf(%d\n,Get_dis(x,y));}
}
