离线然后就是维护加边的动态MST, Link cut tree秒掉..不过我写+调了好久...时间复杂度O(NlogN + MlogM)
-----------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
const int maxn = 100009;
const int maxm = 1000009;
inline int read() {
char c = getchar();
int ret = 0;
for(; !isdigit(c); c = getchar());
for(; isdigit(c); c = getchar())
ret = ret * 10 + c - '0';
return ret;
}
bool F[maxm];
int N, M, Q;
int ans[maxn], r[maxm];
struct Event {
int typ, u, v;
Event(int _typ = 0, int _u = 0, int _v = 0) :
typ(_typ), u(_u), v(_v) {
}
} q[maxn];
struct EDGE {
int u, v, w;
EDGE(int _u = 0, int _v = 0, int _w = 0) : u(_u), v(_v), w(_w) {
}
bool operator < (const EDGE &o) const {
return u < o.u || (u == o.u && v < o.v);
}
} e[maxm];
struct Node* Null;
struct Node {
Node *ch[2], *fa, *par, *c;
int v, Id;
bool rev, isRoot;
inline void Init(int _v) {
ch[0] = ch[1] = fa = par = Null;
v = _v;
c = this;
isRoot = true;
rev = false;
}
inline void setc(Node* t, int v) {
ch[v] = t;
t->fa = this;
}
inline int d() {
return this == fa->ch[1];
}
inline void Rev() {
rev ^= 1;
}
inline void setRoot() {
isRoot = true;
par = fa;
fa = Null;
}
inline void pushDown() {
if(rev) {
swap(ch[0], ch[1]);
ch[0]->Rev();
ch[1]->Rev();
rev = false;
}
}
inline void upd() {
c = ch[0]->c->v > ch[1]->c->v ? ch[0]->c : ch[1]->c;
if(v > c->v)
c = this;
}
} pool[maxn * 3], *Stack[maxn * 3], *V[maxn], *pt;
void Init_LCT() {
pt = pool;
(Null = pt++)->Init(0);
}
Node* newNode(int v, int Id = 0) {
pt->Init(v);
pt->Id = Id;
return pt++;
}
void Rotate(Node* t) {
Node* p = t->fa;
p->pushDown();
t->pushDown();
int d = t->d();
p->fa->setc(t, p->d());
p->setc(t->ch[d ^ 1], d);
t->setc(p, d ^ 1);
p->upd();
if(p->isRoot) {
p->isRoot = false;
t->isRoot = true;
t->par = p->par;
}
}
void Splay(Node* t, Node* f = Null) {
int n = 0;
for(Node* o = t; o != Null; o = o->fa) {
Stack[n++] = o;
}
while(n--)
Stack[n]->pushDown();
for(Node* p = t->fa; p != f; p = t->fa) {
if(p->fa != f)
p->d() != t->d() ? Rotate(t) : Rotate(p);
Rotate(t);
}
t->upd();
}
void Access(Node* t) {
for(Node* o = Null; t != Null; o = t, t = t->par) {
Splay(t);
t->ch[1]->setRoot();
t->setc(o, 1);
}
}
void makeRoot(Node* t) {
Access(t);
Splay(t);
t->Rev();
}
void Cut(Node* x, Node* y) {
makeRoot(x);
Access(y);
Splay(x);
x->setc(Null, 1);
x->upd();
y->setRoot();
y->par = Null;
}
void Join(Node* x, Node* y) {
makeRoot(x);
x->par = y;
}
Node* Path(Node* x, Node* y) {
makeRoot(x);
Access(y);
Splay(y);
return y;
}
void Delete(Node* t) {
Cut(t, V[e[t->Id].u]);
Cut(t, V[e[t->Id].v]);
}
bool cmp(const int &l, const int &r) {
return e[l].w < e[r].w;
}
struct DSU {
int fa[maxn];
void Init() {
for(int i = 0; i < N; i++)
fa[i] = i;
}
int Find(int x) {
return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
bool Unite(int x, int y) {
int _x = Find(x), _y = Find(y);
fa[_x] = _y;
return _x != _y;
}
} dsu;
void BuildMST() {
for(int i = 0; i < M; i++)
r[i] = i;
sort(r, r + M, cmp);
dsu.Init();
for(int i = 0; i < M; i++) if(F[r[i]]) {
if(!dsu.Unite(e[r[i]].u, e[r[i]].v))
continue;
Node* t = newNode(e[r[i]].w, r[i]);
Join(V[e[r[i]].u], t);
Join(V[e[r[i]].v], t);
}
}
void Work() {
for(int i = Q; i--; ) if(q[i].typ == 1) {
ans[i] = Path(V[q[i].u], V[q[i].v])->c->v;
} else {
int d = lower_bound(e, e + M, EDGE(q[i].u, q[i].v, 0)) - e;
if(F[d])
continue;
F[d] = true;
Node* t = Path(V[e[d].u], V[e[d].v]);
if(e[d].w < t->c->v) {
Delete(t->c);
Node* np = newNode(e[d].w, d);
Join(V[e[d].v], np);
Join(V[e[d].u], np);
}
}
for(int i = 0; i < Q; i++)
if(q[i].typ == 1) printf("%d\n", ans[i]);
}
void Init() {
N = read(); M = read(); Q = read();
for(int i = 0; i < M; i++)
F[i] = true;
for(int i = 0; i < M; i++) {
int u = read() - 1, v = read() - 1, w = read();
if(u > v) swap(u, v);
e[i] = EDGE(u, v, w);
}
sort(e, e + M);
for(int i = 0; i < Q; i++) {
int t = read(), u = read() - 1, v = read() - 1;
if(u > v) swap(u, v);
q[i] = Event(t, u, v);
if(t == 2)
F[lower_bound(e, e + M, EDGE(u, v, 0)) - e] = false;
}
Init_LCT();
for(int i = 0; i < N; i++)
V[i] = newNode(0);
}
int main() {
Init();
BuildMST();
Work();
return 0;
}
-----------------------------------------------------------------------
2594: [Wc2006]水管局长数据加强版
Time Limit: 25 Sec Memory Limit: 128 MB
Submit: 1826 Solved: 553
[Submit][Status][Discuss]
Description
SC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。
在处理每项送水任务之前，路径上的水管都要进行一系列的准备操作，如清洗、消毒等等。嘟嘟在控制中心一声令下，这些水管的准备操作同时开始，但由于各条管道的长度、内径不同，进行准备操作需要的时间可能不同。供水公司总是希望嘟嘟能找到这样一条送水路径，路径上的所有管道全都准备就绪所需要的时间尽量短。嘟嘟希望你能帮助他完成这样的一个选择路径的系统，以满足供水公司的要求。另外，由于MY市的水管年代久远，一些水管会不时出现故障导致不能使用，你的程序必须考虑到这一点。
不妨将MY市的水管网络看作一幅简单无向图（即没有自环或重边）：水管是图中的边，水管的连接处为图中的结点。
Input
输入文件第一行为3个整数：N, M, Q分别表示管道连接处（结点）的数目、目前水管（无向边）的数目，以及你的程序需要处理的任务数目（包括寻找一条满足要求的路径和接受某条水管坏掉的事实）。
以下M行，每行3个整数x, y和t，描述一条对应的水管。x和y表示水管两端结点的编号，t表示准备送水所需要的时间。我们不妨为结点从1至N编号，这样所有的x和y都在范围[1, N]内。
以下Q行，每行描述一项任务。其中第一个整数为k：若k=1则后跟两个整数A和B，表示你需要为供水公司寻找一条满足要求的从A到B的水管路径；若k=2，则后跟两个整数x和y，表示直接连接x和y的水管宣布报废（保证合法，即在此之前直接连接x和y尚未报废的水管一定存在）。
Output
按顺序对应输入文件中每一项k=1的任务，你需要输出一个数字和一个回车/换行符。该数字表示：你寻找到的水管路径中所有管道全都完成准备工作所需要的时间（当然要求最短）。
Sample Input
4 4 3
1 2 2
2 3 3
3 4 2
1 4 2
1 1 4
2 1 4
1 1 4
1 2 2
2 3 3
3 4 2
1 4 2
1 1 4
2 1 4
1 1 4
Sample Output
2
3
3
【原题数据范围】
N ≤ 1000
M ≤ 100000
Q ≤ 100000
测试数据中宣布报废的水管不超过5000条；且任何时候我们考虑的水管网络都是连通的，即从任一结点A必有至少一条水管路径通往任一结点B。
【加强版数据范围】
N ≤ 100000
M ≤ 1000000
Q ≤ 100000
任何时候我们考虑的水管网络都是连通的，即从任一结点A必有至少一条水管路径通往任一结点B。
【C/C++选手注意事项】
由于此题输入规模较大（最大的测试点约20MB），因此即使使用scanf读入数据也会花费较多的时间。为了节省读入耗时，建议使用以下函数读入正整数（返回值为输入文件中下一个正整数）：
int getint()
{
char ch = getchar();
for ( ; ch > '9' || ch < '0'; ch = getchar());
int tmp = 0;
for ( ; '0' <= ch && ch <= '9'; ch = getchar())
tmp = tmp * 10 + int(ch) - 48;
return tmp;
}