刘洋网站建设 够完美,遵义做网站的公司,门户网站网页设计规范,城市建设网站aqq【模板】静态仙人掌
题目大意
给你一个无向仙人掌图#xff08;保证每条边至多出现在一个简单回路中的无向图#xff09;#xff0c;问你两个点之间的最短路距离
输入样例#1
9 10 2
1 2 1
1 4 1
3 4 1
2 3 1
3 7 1
7 8 2
7 9 2
1 5 3
1 6 4
5 6 1
1 9
5 7输出样例#1
5
…【模板】静态仙人掌
题目大意
给你一个无向仙人掌图保证每条边至多出现在一个简单回路中的无向图问你两个点之间的最短路距离
输入样例#1
9 10 2
1 2 1
1 4 1
3 4 1
2 3 1
3 7 1
7 8 2
7 9 2
1 5 3
1 6 4
5 6 1
1 9
5 7输出样例#1
5
6输入样例#2
9 10 3
1 2 1
2 3 1
2 4 4
3 4 2
4 5 1
5 6 1
6 7 2
7 8 2
8 9 4
5 9 2
1 9
5 8
3 4输出样例#2
7
5
2样例解释
样例1中的仙人掌是这个样子的
询问有两个分别是询问 1→\rightarrow→ 9和 5→\rightarrow→ 7的最短路 显然答案分别为 5 和 6。
数据范围
1≤n,q≤100001\le n,q \le 100001≤n,q≤10000 1≤m≤200001\le m \le 200001≤m≤20000 1≤w≤1051\le w \le 10^51≤w≤105 请注意时限为 300ms300\text{ms}300ms
解题思路
我们把该图转化为圆方树 建树规则 1对于不在环里面的边我们保留不变 2对于环我们建一个方点黄色的点连接这个该环上所有点边权为为所有点到dfsdfsdfs序最小的点的距离如图 搜索的时候我们记录下某个点的dfsdfsdfs序以及从这个点出发走到的点中dfsdfsdfs序最小的点的dfsdfsdfs序父亲边除外 当我们搜到某个点时枚举到某条边如图红色的边若该边指向的点已经搜过且父亲节点不是该点且dfs序大于该点那么我们搜到了一个环且这个环中dfsdfsdfs序最小的点就是该点 dfsdfsdfs序大于该点很显然是该点出发搜索到的点 且与该点相连那么肯定是一个环了 从该点出发一边是从该点搜索到的点且dfs序逐渐变大dfsdfsdfs序大于该点另一边是红色边的点dfsdfsdfs序也大于该点 那么该点就是该环所有点中dfsdfsdfs序最小的点 我们像这样建树 然后得到了一棵圆方数 对于树上两点的最短距离 就是两点到lcalcalca的距离 若lcalcalca不是方点但经过方点那经过该环的距离就是走到dfsdfsdfs序最小的点最短的距离也就是从该环中某个圆点到方点再到dfsdfsdfs序最小的点的距离所以没有影响
对于lcalcalca是方点的我们先计算到该环某个圆点的距离然后求到对方点的最小距离即可就是两个方向距离的minminmin
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
using namespace std;
ll n, m, w, x, y, z, q, X, Y, ex, ans, tot, tott, b[100010], fa[200010], dep[200010], dis[200010], sum[200010], dfn[200010], low[200010], h[200010], head[200010], f[200010][20];
struct rec
{ll to, l, next;
}e[2000010], a[2000010];
int read()//快读
{char xgetchar();int d1,l0;while (x0||x9) {if (x-) d-1;xgetchar();}while (x0x9) l(l3)(l1)x-48,xgetchar();return l*d;
}
void writ(int c) {if (c9) writ(c/10); putchar(c%1048); return;}
void write(int s) {s0?putchar(45),writ(-s):writ(s); putchar(10); return;}
void add(ll x, ll y, ll z)//加圆方树的边
{a[tot].to y;a[tot].l z;a[tot].next head[x];head[x] tot;a[tot].to x;a[tot].l z;a[tot].next head[y];head[y] tot;
}
void addd(ll x, ll y, ll z)//加原图的边
{e[tott].to y;e[tott].l z;e[tott].next h[x];h[x] tott;e[tott].to x;e[tott].l z;e[tott].next h[y];h[y] tott;
}
void jh(ll x, ll y, ll z)//对于环建圆方树
{ex;ll pt y, ss z;while(pt ! fa[x])//求从x到所有点走反边的距离红色边的方向{sum[pt] ss;ss b[pt];//求和pt fa[pt];}sum[ex] sum[x];sum[x] 0;pt y;ss 0;while(pt ! fa[x]){ss min(sum[pt], sum[ex] - sum[pt]);//走两条边中最短的add(pt, ex, ss);//加边pt fa[pt];}
}
void dfs(ll x)
{dfn[x] low[x] w;for (int i h[x]; i; i e[i].next)if (e[i].to ! fa[x]) {ll v e[i].to;if (!dfn[v])//没走过{fa[v] x;b[v] e[i].l;//记录dfs(v);low[x] min(low[x], low[v]);//记录由该点走出去的点中dfs序最小的}else low[x] min(low[x], dfn[v]);//到过了要不就是走回了变if (low[v] dfn[x]) add(x, v, e[i].l);}for (int i h[x]; i; i e[i].next)if ( dfn[e[i].to] dfn[x] fa[e[i].to] ! x)jh(x, e[i].to, e[i].l);
}
void dfs1(int x)
{dep[x] dep[f[x][0]] 1;for (int j 1; j 16; j)f[x][j] f[f[x][j - 1]][j - 1];//倍增for (int i head[x]; i; i a[i].next)if (a[i].to ! f[x][0]){f[a[i].to][0] x;if (dis[a[i].to]) dis[a[i].to] min(dis[a[i].to], dis[x] a[i].l);else dis[a[i].to] dis[x] a[i].l;dfs1(a[i].to);}
}
ll lca(ll x, ll y)
{if (dep[x] dep[y]) swap(x, y);//求lcafor (int i 16; i 0; --i)if (dep[f[x][i]] dep[y]) x f[x][i];for (int i 16; i 0; --i)if (f[x][i] ! f[y][i]) x f[x][i], y f[y][i];X x;//若两点不是祖先关系那会停留在前一个点Y y;return x y?x:f[x][0];
}
int main()
{n read();m read();q read();ex n;for (int i 1; i m; i){x read();y read();z read();addd(x, y, z);}dfs(1);f[1][0] 1;dfs1(1);for (int i 1; i q; i){x read();y read();z lca(x, y);if (z n) ans dis[x] dis[y] - dis[z] - dis[z];//lca是圆点else{ans dis[x] - dis[X] dis[y] - dis[Y]; //到环上两圆点的距离if (sum[X] sum[Y]) swap(X, Y);ans min(sum[Y] - sum[X], sum[z] - sum[Y] sum[X]);//环的两个方向}write(ans);}return 0;
}
