分类 带权并查集 下的文章

BZOJ 1202: [HNOI2005]狡猾的商人

Solution题目相当于给出几组前缀和 s[r] - s[l-1]。所以用带权并查集维护一下和根的距离就可以了。Code#include <cstdio> #include <algorithm> using namespace std; const int N = 1000; int n, m; int fa[N], dis[N]; int father(int x) { if(fa[x] == x) return x; int t = father(fa[x]); dis[x] += dis[fa[x]]; fa- 阅读剩余部分 -

BZOJ 3362: [Usaco2004 Feb]Navigation Nightmare 导航噩梦

题目描述农夫约翰有N(2≤N≤40000)个农场,标号1到N,M(2≤M≤40000)条的不同的垂直或水平的道路连结着农场,道路的长度不超过1000.这些农场的分布就像下面的地图一样,图中农场用F1..F7表示, 每个农场最多能在东西南北四个方向连结4个不同的农场.此外,农场只处在道路的两端.道路不会交叉且每对农场间有且仅有一条路径.邻居鲍伯要约翰来导航,但约翰丢了农场的地图,他只得从电脑的备份中修复了.每一条道路的信息如下:从农场23往南经距离10到达农场17从农场1往东经距离7到达农场17当约翰重新获得这些数据时,他有时被的鲍伯的问题打断:“农场1到农场23的曼哈顿距离- 阅读剩余部分 -