LOJ121 动态图连通性（离线可过）题解

传送门 LOJ121

询问两个点是否连通其实就是要从一个点走到另一个点。

本题允许离线，我们可以预处理出第$i$条边被删除的时间，记为$t_i$。

由于边有可能被删除，我们在从一个点走到另一个点的时候总是希望走那些晚些被删除的边，也就是说最小的$t_i$尽可能大的边。是不是有点像NOIP2013的货车运输？

所以我们只要按$t_i$动态维护最大生成树即可。LCT可以很好地完成这个工作。

#include 
#include 
#include 
#include 
#include 
#include template <typename T> inline void read(T& t) {int f = 0, c = getchar(); t = 0;while (!isdigit(c)) f |= c == '-', c = getchar();while (isdigit(c)) t = t * 10 + c - 48, c = getchar();if (f) t = -t;
}
#if __cplusplus >= 201103L
template <typename T, typename... Args>
inline void read(T& t, Args&... args) {read(t); read(args...);
}
#else
template <typename T1, typename T2>
inline void read(T1& t1, T2& t2) { read(t1); read(t2); }
template <typename T1, typename T2, typename T3>
inline void read(T1& t1, T2& t2, T3& t3) { read(t1, t2); read(t3); }
template <typename T1, typename T2, typename T3, typename T4>
inline void read(T1& t1, T2& t2, T3& t3, T4& t4) { read(t1, t2, t3); read(t4); }
template <typename T1, typename T2, typename T3, typename T4, typename T5>
inline void read(T1& t1, T2& t2, T3& t3, T4& t4, T5& t5) { read(t1, t2, t3, t4); read(t5); }
#endif  // C++11#ifdef WIN32
#define LLIO "%I64d"
#else
#define LLIO "%lld"
#endif  // WIN32 long long
#define rep(I, A, B) for (int I = (A); I <= (B); ++I)
#define rrep(I, A, B) for (int I = (A); I >= (B); --I)
#define erep(I, X) for (int I = head[X]; I; I = next[I])const int maxn = 5e3 + 207, maxm = 5e5 + 207, maxsize = maxn + maxm;
int fa[maxsize], ch[maxsize][2], value[maxsize], mp[maxsize];
bool rev[maxsize];
struct Edge {int x, y, w;explicit Edge(int a, int b, int c): x(a), y(b), w(c) {}Edge() : x(0), y(0), w(0) {}
};
Edge e[maxm];
struct Query {int q, x, y, pos;
};
Query q[maxm];
std::map<std::pair<int, int>, int> id;
int n, m, tot;template <> inline void read(Query& qq) {read(qq.q, qq.x, qq.y);
}inline int iden(int x) {if (ch[fa[x]][0] == x) return 0;if (ch[fa[x]][1] == x) return 1;return -1;
}
inline void update(int x) {mp[x] = x;rep(i, 0, 1) if (ch[x][i] && value[mp[ch[x][i]]] < value[mp[x]])mp[x] = mp[ch[x][i]];
}
inline void pushdown(int x) {if (rev[x]) {rev[ch[x][0]] ^= 1;rev[ch[x][1]] ^= 1;rev[x] = 0;std::swap(ch[x][0], ch[x][1]);}
}
inline void rotate(int x) {if (!x) return;int d = iden(x), y = fa[x];if (~iden(y)) ch[fa[y]][iden(y)] = x;fa[x] = fa[y];if ((ch[y][d] = ch[x][d ^ 1]))fa[ch[x][d ^ 1]] = y;fa[ch[x][d ^ 1] = y] = x;update(y); update(x);
}
int s[maxsize];
inline void splay(int x) {int t = 0;for (int i = x;; i = fa[i]) {s[++t] = i;if (!~iden(i)) break;}while (t) pushdown(s[t--]);while (~iden(x)) {int y = fa[x];if (~iden(y)) rotate(iden(y) ^ iden(x) ? x : y);rotate(x);}
}
inline void access(int x) {for (int y = 0; x; x = fa[y = x]) {splay(x); ch[x][1] = y; update(x);}
}
inline void makeroot(int x) {access(x); splay(x); rev[x] ^= 1;
}
inline void link(int x, int y) {makeroot(x); fa[x] = y;
}
inline void cut(int x, int y) {makeroot(x); access(y); splay(y);if (ch[y][0] == x) {fa[x] = ch[y][0] = 0;update(y);}
}
inline int findroot(int x) {access(x); splay(x);while (pushdown(x), ch[x][0]) x = ch[x][0];splay(x);return x;
}
inline bool connected(int x, int y) {return findroot(x) == findroot(y);
}
inline void split(int x, int y) {makeroot(x); access(y); splay(y);
}int main() {read(n, m);rep(i, 1, n) value[i] = INT_MAX, mp[i] = i;rep(i, 1, m) {read(q[i]);if (q[i].x > q[i].y) std::swap(q[i].x, q[i].y);if (!q[i].q) {e[++tot] = Edge(q[i].x, q[i].y, m + 1);id[std::make_pair(q[i].x, q[i].y)] = tot;q[i].pos = tot;} else if (q[i].q == 1) {int d = id[std::make_pair(q[i].x, q[i].y)];q[i].pos = d;e[d].w = i;}}rep(i, 1, tot) value[i + n] = e[i].w, mp[i + n] = i + n;rep(i, 1, m) {int c = q[i].q, x = q[i].x, y = q[i].y, p = q[i].pos;if (!c) {if (!connected(x, y)) {link(x, p + n);link(p + n, y);} else {split(x, y);int d = mp[y] - n;if (e[p].w > e[d].w) {cut(e[d].x, d + n);cut(d + n, e[d].y);link(x, p + n);link(p + n, y);}}} else if (c == 1) {cut(x, p + n);cut(p + n, y);} elseputs(connected(x, y) ? "Y" : "N");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！