[BZOJ 5415] 归程
2024-09-25 17:58:08
一棵KrusKal重构树,然而我数组开小了,忘记清空一个标记
洛谷传送门
BZOJ传送门 ......好像成权限题了Orz
回顾我们用KrusKal做生成树的时候,我们将边排序后连通各个连通块,那么边一定是单调的。
所以我们考虑维护一颗最大生成树,然后查询时倍增就好了,复杂度 n * log n
RE代码,把注释的删了就好了,数组没开够
#include <cstdio> #include <algorithm> #include <queue> #include <cstring> #include <cctype> using namespace std; , M = 1e6 + , inf = 0x7fffffff; int v[M], to[M], head[N], pos[M], p; void build(int a, int b, int c) { v[++ p] = b; to[p] = head[a]; head[a] = p; pos[p] = c; } void link(int a, int b, int c) { build(a, b, c); build(b, a, c); } int pre[N], far[N], n; int find(int x) { return pre[x] == x ? x : pre[x] = find(pre[x]); } struct point { int d, f; point (int d, int f) : d(d), f(f) {} point () {} bool operator < (const point &a) const { return f > a.f; } }; priority_queue<point> tp; void dijkstra() { ; i <= n; ++ i) far[i] = inf; tp.push(point(, )); while( !tp.empty()) { int u = tp.top().d; tp.pop(); for ( int i = head[u]; i; i = to[i]) if( far[v[i]] > far[u] + pos[i]) { far[v[i]] = far[u] + pos[i]; tp.push(point(v[i], far[v[i]])); } } } ], cnt; int query(int a, int P) { ; i >= ; -- i) if( POS[T[a][i]] > P) a = T[a][i]; return far[a]; } struct node { int u, v, val; node ( int u, int v, int val) : u(u), v(v), val(val) {} node () {} bool operator < (const node &a) const { return val > a.val; } }tc[M]; int lastans, Case, m, q, K, s; inline void G(int &x) { x = ; ; ; ) + (x << ) + (o & ); x *= f; } ]; int main() { freopen("return1.in", "r", stdin); freopen("return.out", "w", stdout); G(Case); while( Case -- ) { G(n), G(m); ; i <= n; ++ i) head[i] = ; // p = 0; // 当时好像是因为没加这个RE了....... , a, b, c, d; i <= m; ++ i) G(a), G(b), G(c), G(d), tc[i] = node(a, b, d), link(a, b, c); sort(tc+, tc++m); dijkstra(); ; i <= n; ++ i) pre[i] = i, POS[i] = inf; cnt = n; ; i <= m; ++ i) { if( find(tc[i].u) == find(tc[i].v)) continue; int A = find(tc[i].u), B = find(tc[i].v); ++ cnt; POS[cnt] = tc[i].val; far[cnt] = min(far[A], far[B]); T[A][] = T[B][] = cnt; pre[cnt] = pre[A] = pre[B] = cnt; } T[cnt][] = T[cnt][] = cnt; ; i <= ; ++ i) ; k <= cnt; ++ k) T[k][i] = T[T[k][i-]][i-]; G(q); G(K); G(s); cnt = lastans = ; , v0, p0; i <= q; ++ i) { G(v0); G(p0); ) % n + , p0 = (p0 + K * lastans) % (s + ); lastans = query(v0, p0); int t = lastans; , t /= ; while( t); '+TP[cnt]); puts(""); } } ; }
woc, 差点忘了这个
最新文章
- R abalone data set
- python-汉诺塔递归实现
- 关于iOS6应用中第三方类库不支持armv7s的问题解决
- C++实现离散余弦变换(参数为二维指针)
- SDC(6)&ndash;I/O约束
- 定制属于自己的自动化安装的linux系统镜像
- Flash正则例子
- maven 项目 pom.xml文件中配置的jar包下载报错
- 使用flex
- 数据结构-堆(应用篇)之堆排序法-C和C++的实现
- JavaScript设计模式 Item 5 --链式调用
- DSAPI 网页获取本地程序登陆用户
- [Javasript] 同时实现单击和双击事件
- Thymeleaf中的&;&;解析问题
- python中安装request模块
- 【算法专题】工欲善其事必先利其器—— 常用函数和STL
- HDU 1431 素数回文
- linux系统编程之管道(一):匿名管道(pipe)
- c#总结:datatable的方法大全
- CSS之旋转立方体