问题 B: 【2022NOIP联测2 10月2日】最短路问题 V3
我把我写的这个改了改格式去最短路的专题里都能A某些东西,比如:信使,对,这题的数据很水,但是我把它交到accoders上不是T了而是错了!!WA 20……这有点离谱?然后注释掉的就是这个B的错误写法:有大佬知道它为什么不对吗***
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 500; const ll inf = 1e17; int n, m, q, ff[maxn], stk[maxn], cnt, id[maxn]; ll ans, dis[maxn]; bool vis[maxn]; inline int read() { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') { f = -1; } ch = getchar(); } while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch^48); ch = getchar(); } return x * f; } struct node { int next, to, w; }a[maxn<<1], e[maxn<<1]; int len, tot, head[maxn], h[maxn]; void add(int x, int y, int w) { a[++len].to = y; a[len].next = head[x]; a[len].w = w; head[x] = len; } void add_tree(int x, int y, int w) { e[++tot].to = y; e[tot].next = h[x]; e[tot].w = w; h[x] = tot; } inline void New(int x) {if(id[x]) return; stk[++cnt] = x; id[x] = cnt;} int fa[maxn], dep[maxn], siz[maxn], son[maxn], top[maxn]; void find_heavy_edge(int u, int fat, int depth) { //printf("u = %d\n", u); fa[u] = fat; dep[u] = depth; siz[u] = 1; son[u] = 0; int maxsize = 0; for(int i=h[u]; i; i=e[i].next) { int v = e[i].to; if(dep[v]) continue; dis[v] = dis[u] + e[i].w; find_heavy_edge(v, u, depth+1); siz[u] += siz[v]; if(siz[v] > maxsize) { maxsize = siz[v]; son[u] = v; } } } void connect_heavy_edge(int u, int ancestor) { top[u] = ancestor; if(son[u]) { connect_heavy_edge(son[u], ancestor); } for(int i=h[u]; i; i=e[i].next) { int v = e[i].to; if(v == son[u] || v == fa[u]) continue; connect_heavy_edge(v, v); } } int LCA(int x, int y) { while(top[x] != top[y]) { if(dep[x] < dep[y]) swap(x, y); x = fa[top[x]]; //printf("x = %d y = %d\n", x, y); } if(dep[x] > dep[y]) swap(x, y); return x; } int find(int x) { if(x == ff[x]) return x; return ff[x] = find(ff[x]); } queue<int> qu; ll d[44][maxn]; void spfa(int st) { for(int i=1; i<=n; i++) d[id[st]][i] = inf; d[id[st]][st] = 0; vis[st] = 1; qu.push(st); while(!qu.empty()) { int x = qu.front(); qu.pop(); vis[x] = 0; for(int i=head[x]; i; i=a[i].next) { int y = a[i].to; if(d[id[st]][y] > d[id[st]][x] + a[i].w) { d[id[st]][y] = d[id[st]][x] + a[i].w; if(!vis[y]) { vis[y] = 1; qu.push(y); } } } } } int main() { //freopen("1.in", "r", stdin); n = read(); m = read(); for(int i=1; i<=n; i++) ff[i] = i; for(int i=1; i<=m; i++) { int u = read(), v = read(), w = read(); add(u, v, w); add(v, u, w); int fx = find(u), fy = find(v); if(fx == fy) { New(u); New(v); continue; } ff[fx] = fy; add_tree(u, v, w); add_tree(v, u, w); } find_heavy_edge(1, 0, 1); connect_heavy_edge(1, 1); for(int i=1; i<=cnt; i++) { spfa(stk[i]); } /*q = read(); while(q--) { int u = read(), v = read(); int lca = LCA(u, v); ans = dis[u] + dis[v] - dis[lca] - dis[lca]; for(int i=1; i<=cnt; i++) { ans = min(ans, d[i][u]+d[i][v]); } printf("%lld\n", ans); }*/ ll res = 0; for(int i=2; i<=n; i++) { int lca = LCA(1, i); res = dis[i] - dis[lca] - dis[lca]; for(int j=1; j<=cnt; j++) { res = min(res, d[j][1]+d[j][i]); } //printf("res[%d] = %lld\n", i, res); ans = max(ans, res); } printf("%lld\n", ans); return 0; }View Code
标签:ch,int,18,模测,top,son,maxn,2022,ll From: https://www.cnblogs.com/Catherine2006/p/16748884.html