P4149 距离为K的点对(最少边数) n=200000 点分治
2024-09-04 05:22:27
这题数据范围变成了200000 n^2就过不了 同时要求求的是最少的边数 不能容斥
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + ;
const int MAXM = 2e5 + ;
int to[MAXM << ], nxt[MAXM << ], Head[MAXN], ed = ;
int cost[MAXM << ];
int ok[];
inline void addedge(int u, int v, int c) {
to[++ed] = v;
cost[ed] = c;
nxt[ed] = Head[u];
Head[u] = ed;
}
inline void ADD(int u, int v, int c) {
addedge(u, v, c);
addedge(v, u, c);
}
int n, anser, k, cnt;
int sz[MAXN], f[MAXN], dep[MAXN], sumsz, root;
bool vis[MAXN];
pair<int, int> o[MAXN];
int num[MAXN];
void getroot(int x, int fa) {
sz[x] = ;
f[x] = ;
for (int i = Head[x]; i; i = nxt[i]) {
int v = to[i];
if (v == fa || vis[v]) {
continue;
}
getroot(v, x);
sz[x] += sz[v];
f[x] = max(f[x], sz[v]);
}
f[x] = max(f[x], sumsz - sz[x]);
if (f[x] < f[root]) {
root = x;
}
}
void getdeep(int x, int fa, int deep) {
if (dep[x] > k) {
return;
}
o[++cnt] = make_pair(dep[x], deep);
num[++num[]] = dep[x];
for (int i = Head[x]; i; i = nxt[i]) {
int v = to[i];
if (v == fa || vis[v]) {
continue;
}
dep[v] = dep[x] + cost[i];
getdeep(v, x, deep + );
}
}
void calc(int x, int d) {
num[] = ;
dep[x] = d;
for (int i = Head[x]; i; i = nxt[i]) {
int v = to[i];
if (vis[v]) {
continue;
}
cnt = ;
dep[v] = dep[x] + cost[i];
getdeep(v, x, );
for (int j = ; j <= cnt; j++) {
if (o[j].first <= k) {
if (ok[k - o[j].first] != INT_MAX) {
anser = min(anser, ok[k - o[j].first] + o[j].second);
}
}
}
for (int j = ; j <= cnt; j++) {
if (o[j].first <= k) {
ok[o[j].first] = min(o[j].second, ok[o[j].first]);
}
}
}
for (int i = ; i <= num[]; i++) {
ok[num[i]] = INT_MAX;
}
}
void solve(int x) {
vis[x] = ;
calc(x, );
int totsz = sumsz;
for (int i = Head[x]; i; i = nxt[i]) {
int v = to[i];
if (vis[v]) {
continue;
}
root = ;
sumsz = sz[v] > sz[x] ? totsz - sz[x] : sz[v];
getroot(v, );
solve(root);
}
}
int main() {
scanf("%d %d", &n, &k);
anser = INT_MAX;
for (int i = ; i <= k; i++) {
ok[i] = INT_MAX;
}
cnt = ;
memset(Head, , sizeof(Head));
memset(vis, , sizeof(vis));
ed = ;
int u, v, c;
for (int i = ; i < n; i++) {
scanf("%d %d %d", &u, &v, &c);
ADD(u + , v + , c);
}
root = , sumsz = f[] = n;
getroot(, );
solve(root);
printf("%d\n", anser == INT_MAX ? - : anser);
return ;
}
注意dep[x]>k的时候要return 不然会re
最新文章
- [译]libev和libevent的设计差异
- redis 学习 01(下载 学习资源)
- 【BZOJ-4522】密钥破解 数论 + 模拟 ( Pollard_Rho分解 + Exgcd求逆元 + 快速幂 + 快速乘)
- web中session与序列化的问题
- PAT乙级 1028. 人口普查(20)
- Myeclipse优化篇
- 再起航,我的学习笔记之JavaScript设计模式01
- css 块元素、内联元素、内联块元素
- jquery学习-document.ready和document.onload区别
- PHP中new static()与new self()的区别异同分析
- vijos 1605 双栈排序 - 贪心 - 二分图
- 一个类似于jq的小型库
- 洛谷P3868 [TJOI2009]猜数字(中国剩余定理,扩展欧几里德)
- TCGA phenotype各列的含义
- centos shell编程3【告警系统】 没有服务器端和客户端的概念 main.sh mon.conf load.sh 502.sh mail.php mail.sh disk.sh 第三十七节课
- Mybatis中的几种注解映射
- 如何实现php异步处理
- LDA算法里面Dirichlet分布的两个参数alpha和beta怎样确定?
- HighCharts 在IE8下饼图不显示的问题
- 经典C#面试题
热门文章
- 【DSP开发】DSP程序优化
- java8函数式接口(Functional Interface)
- day16 模块导入及环境变量
- [Agc036D]Do Not Duplicate_链表_贪心_数论
- Redis(1.11)Redis4.0.11 cluster 分布式集群搭建
- 对Redis 单进程、单线程模型的理解(网摘)
- 了解WebSocket
- golang 环境配置 over centos7
- Hystrix服务容错保护
- Java EE javax.servlet中的RequestDispatcher接口