[WC2006]水管局长数据加强版
时间限制：5 s 内存限制：1024 MB
【题目描述】
SC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。
在处理每项送水任务之前，路径上的水管都要进行一系列的准备操作，如清洗、消毒等等。嘟嘟在控制中心一声令下，这些水管的准备操作同时开始，但由于各条管道的长度、内径不同，进行准备操作需要的时间可能不同。供水公司总是希望嘟嘟能找到这样一条送水路径，路径上的所有管道全都准备就绪所需要的时间尽量短。嘟嘟希望你能帮助他完成这样的一个选择路径的系统，以满足供水公司的要求。另外，由于MY市的水管年代久远，一些水管会不时出现故障导致不能使用，你的程序必须考虑到这一点。
不妨将MY市的水管网络看作一幅简单无向图（即没有自环或重边）：水管是图中的边，水管的连接处为图中的结点。
【输入格式】
输入文件第一行为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尚未报废的水管一定存在）。
【输出格式】
按顺序对应输入文件中每一项k=1的任务，你需要输出一个数字和一个回车/换行符。该数字表示：你寻找到的水管路径中所有管道全都完成准备工作所需要的时间（当然要求最短）。
【样例输入】
4 4 3 1 2 2 2 3 3 3 4 2 1 4 2 1 1 4 2 1 4 1 1 4
【样例输出】
2
3【原题数据范围】N ≤ 1000M ≤ 100000Q ≤ 100000测试数据中宣布报废的水管不超过5000条；且任何时候我们考虑的水管网络都是连通的，即从任一结点A必有至少一条水管路径通往任一结点B。【加强版数据范围】N ≤ 100000M ≤ 1000000Q ≤ 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; } 【来源】
鸣谢Kac
【题目来源】
耒阳大世界（衡阳八中） OJ 2594
首先，这道题是在维护边上的信息，于是需要“化边为点”，具体做法就是把一条连接x和y的边，变成两条，x->z,z->y，而z节点存贮的就是这条边的信息，同时用map来保存两点间边的编号方便下面使用(我想不到更好的办法了...dalao们有的话请赐教...最好附上证明...),这样我们就把维护边变成了维护点。
首先我们需要知道一个结论，一张图的最小生成树也是这张图的最小瓶颈生成树，就是保证每两点间距离的最大值最小，这个也很好证明，假设求出的最小生成树的连边分别为x->y,y->z，那么我们假设存在一条边x->z使得每两点间距离最大值更小，那么删去x->y和y->z中较大的那条边，再链上x->z这条边，这是一颗更小的生成树，与已知矛盾，所以最小生成树即为最小瓶颈生成树。
那么最直接的方法就是先跑一遍kruskal，然后对于每一个2操作，判断是否在当前图中，然后在执行cut啊link等操作，但是，我们会发现，link哪条边呢？？？？所以其实正向想并不好求，于是考虑反过来想，先把该报废的都报废了，再跑一遍kruskal，倒着处理，每一次2操作看一下其所连端点的路径中最大值是不是大于当前边，大于的话删除那条最大的，加入当前边，可以得到一棵更小的生成树。
但是，看下面一组数据(已加至cogs)：
4 3 3
1 2 2
2 3 3
2 4 1
1 1 3
2 2 3
2 2 4
我们会发现还有一个问题需要注意，就是倒序处理到2操作的时候，当前边所连的两个点可能根本不连通(因为我们是对未删除的边进行kruskal，如果查询一次之后删除了所有的边，这种情况kruskal求得的并不是一个联通的图，倒序处理也会出一些问题)，这时需要特判一下。
附上我的代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int inf=1100005; 4 int n,m,query,pa[inf/10]; 5 struct edge{ 6 int from,to,cost,flag; 7 bool operator < (const edge &o)const{ 8 return cost<o.cost; 9 } 10 }e[inf]; 11 struct Q{ 12 int k,x,y,ans; 13 }q[inf/10]; 14 map<int,int>S[inf/10]; 15 int ch[inf][2],fa[inf],val[inf],rev[inf],ms[inf]; 16 int get_pa(int x){ 17 return pa[x]==x?x:pa[x]=get_pa(pa[x]); 18 } 19 bool get(int x){ 20 return ch[fa[x]][1]==x; 21 } 22 bool isroot(int x){ 23 return ch[fa[x]][1]!=x&&ch[fa[x]][0]!=x; 24 } 25 void update(int x){ 26 ms[x]=x; 27 int ls=ch[x][0],rs=ch[x][1]; 28 if(val[ms[ls]]>val[ms[x]])ms[x]=ms[ls]; 29 if(val[ms[rs]]>val[ms[x]])ms[x]=ms[rs]; 30 } 31 void pushdown(int x){ 32 if(!rev[x])return ; 33 rev[x]=0; 34 int ls=ch[x][0],rs=ch[x][1]; 35 rev[ls]^=1;rev[rs]^=1; 36 swap(ch[ls][0],ch[ls][1]); 37 swap(ch[rs][0],ch[rs][1]); 38 } 39 void zig(int x){ 40 int old=fa[x],oldf=fa[old]; 41 pushdown(old); 42 pushdown(x); 43 bool p=get(x); 44 if(!isroot(old))ch[oldf][get(old)]=x; 45 fa[x]=oldf; 46 fa[ch[old][p]=ch[x][p^1]]=old; 47 fa[ch[x][p^1]=old]=x; 48 update(old); 49 update(x); 50 } 51 void splay(int x){ 52 for(;!isroot(x);zig(x)) 53 if(!isroot(fa[x]))zig(get(x)==get(fa[x])?fa[x]:x); 54 pushdown(x); 55 } 56 void access(int x){ 57 int last=0; 58 while(x){ 59 splay(x); 60 ch[x][1]=last; 61 update(x); 62 last=x; 63 x=fa[x]; 64 } 65 } 66 void makeroot(int x){ 67 access(x); 68 splay(x); 69 rev[x]^=1; 70 swap(ch[x][0],ch[x][1]); 71 } 72 void link(int x,int y){ 73 makeroot(x); 74 fa[x]=y; 75 } 76 void cut(int x,int y){ 77 makeroot(x); 78 access(y); 79 splay(y); 80 fa[x]=ch[y][0]=0; 81 update(y); 82 } 83 int Q(int x,int y){ 84 makeroot(x); 85 access(y); 86 splay(y); 87 return ms[y]; 88 } 89 void kruskal(){ 90 int ned=n-1; 91 for(int i=1;i<=m;i++){ 92 if(e[i].flag)continue; 93 int pax=get_pa(e[i].from),pay=get_pa(e[i].to); 94 if(pax==pay)continue; 95 if(rand()%2)pa[pax]=pay; 96 else pa[pay]=pax; 97 link(i+n,e[i].from);link(i+n,e[i].to); 98 ned--; 99 if(!ned)break; 100 } 101 } 102 int main() 103 { 104 scanf("%d%d%d",&n,&m,&query); 105 for(int i=1;i<=m;i++){ 106 scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].cost); 107 } 108 for(int i=1;i<=n;i++)pa[i]=i; 109 sort(e+1,e+m+1); 110 for(int i=1;i<=m;i++){ 111 S[e[i].from][e[i].to]=S[e[i].to][e[i].from]=i; 112 val[i+n]=e[i].cost; 113 } 114 for(int i=1;i<=query;i++){ 115 scanf("%d%d%d",&q[i].k,&q[i].x,&q[i].y); 116 if(q[i].k==2){ 117 e[S[q[i].x][q[i].y]].flag=1; 118 } 119 } 120 kruskal(); 121 for(int i=query;i>=1;i--){ 122 if(q[i].k==1){ 123 int t=Q(q[i].x,q[i].y); 124 q[i].ans=val[t]; 125 } 126 else { 127 int u=S[q[i].x][q[i].y]; 128 int pax=get_pa(q[i].x),pay=get_pa(q[i].y); 129 if(pax!=pay){ 130 if(rand()%2)pa[pax]=pay; 131 else pa[pay]=pax; 132 link(u+n,q[i].x);link(u+n,q[i].y); 133 continue; 134 } 135 int t=Q(q[i].x,q[i].y); 136 if(e[u].cost>=val[t])continue; 137 cut(t,e[t-n].from);cut(t,e[t-n].to); 138 link(u+n,q[i].x);link(u+n,q[i].y); 139 } 140 } 141 for(int i=1;i<=query;i++)if(q[i].k==1)printf("%d\n",q[i].ans); 142 return 0; 143 }