| 记录编号 |
303727 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[WC 2006] 水管局长 |
最终得分 |
100 |
| 用户昵称 |
 Hzoi_chairman |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
4.862 s |
| 提交时间 |
2016-09-06 16:24:55 |
内存使用 |
50.65 MiB |
显示代码纯文本
/*
Name: 水管局长
Copyright:
Author: chairman
Date: 06/09/16 16:17
Description: 需要找出瓶颈生成树，kruskal跑出来就是瓶颈生成树
证明：如果跑出来的不是瓶颈生成树，则一定可以从枚举过却未选的边中选择替换，但这样会使更靠前的边不选择，不满足最小
跑出来后，倒序处理，进行加边操作，每次如果可加边，都再树剖一遍
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define maxn 2020
#define maxe 200100
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int read()
{
int x,f=1;
char ch;
while(ch=getchar(),!isdigit(ch))
{
if(ch=='-')f=-1;
}
x=ch-48;
while(ch=getchar(),isdigit(ch))
{
x=x*10+ch-48;
}
return x*f;
}
void write(int x)
{
if(x<0)putchar('-'),x=-x;
int cnt=0;char ch[30];
while(ch[++cnt]=x%10+48,x/=10);
while(putchar(ch[cnt]),--cnt);
putchar('\n');
}
struct edge
{
int t,n,f,d;
}a[maxe],e[maxe];
int len,len1,head[maxn];
void insert(int x,int y,int z)
{
e[++len].f=x;e[len].t=y;e[len].d=z;
}
void add(int x,int y,int z)
{
a[++len1].f=x;a[len1].t=y;a[len1].d=z;a[len1].n=head[x];head[x]=len1;
}
int ra[maxn<<2],id[maxn],pos[maxn],cnt,val[maxn],mp[maxn][maxn],dis[maxn][maxn],ans[maxe],n,m,q,type[maxe],from[maxe],to[maxe],ff[maxn][maxn],size[maxn],son[maxn],rt[maxn],fa[maxn],d[maxn],tp[maxn];
//注意ra一定要开大，否则会越界
//mp表示两点之间的边的编号，dis表示两点之间的距离，ff表示该两点之间的边不可用
int find(int x)
{
int xx=x,y;
while(rt[xx]!=xx)xx=rt[xx];
while(rt[x]!=xx)y=rt[x],rt[x]=xx,x=y;
return xx;
}
bool com(const edge &a,const edge &b)
{
return a.d<b.d;
}
void kruskal()
{
sort(e,e+1+len,com);
int cnt=0;
for(int i=1;i<=len;i++)
{
int fx=find(e[i].f),fy=find(e[i].t);
if(fx==fy||ff[e[i].f][e[i].t])continue;
rt[fx]=fy;
add(e[i].f,e[i].t,e[i].d);
add(e[i].t,e[i].f,e[i].d);
mp[e[i].f][e[i].t]=len1-1;
mp[e[i].t][e[i].f]=len1;
cnt++;
if(cnt==n-1)break;
}
}
#define k a[i].t
void dfs1(int x)
{
size[x]=1;
for(int i=head[x];i;i=a[i].n)
{
if(fa[x]==k||k==-1)continue;
fa[k]=x;d[k]=d[x]+1;
val[k]=i;
dfs1(k);
size[x]+=size[k];
if(size[son[x]]<size[k])son[x]=k;
}
}
void dfs2(int x,int top)
{
tp[x]=top;id[x]=++cnt;pos[cnt]=x;
if(son[x])dfs2(son[x],top);
for(int i=head[x];i;i=a[i].n)
{
if(k==son[x]||fa[x]==k||k==-1)continue;
dfs2(k,k);
}
}
#undef k
void build(int rt,int l,int r)
{
if(l==r)
{
ra[rt]=val[pos[l]];
return ;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
if(a[ra[rt<<1]].d<a[ra[rt<<1|1]].d)ra[rt]=ra[rt<<1|1];
else ra[rt]=ra[rt<<1];
}
int query(int rt,int l,int r,int x,int y)
{
if(x<=l&&y>=r)
{
return ra[rt];
}
int mid=(l+r)>>1;
int aa=0,b=0;
if(x<=mid)aa=query(lson,x,y);
if(y>mid)b=query(rson,x,y);
if(a[aa].d<a[b].d)return b;
else return aa;
}
int lca(int x,int y,int p)
{
int ans=0;
int fx=tp[x],fy=tp[y];
while(fx!=fy)
{
if(d[fx]<d[fy])swap(fx,fy),swap(x,y);
int tem=query(1,1,n,id[fx],id[x]);
if(a[ans].d<a[tem].d)ans=tem;
x=fa[fx];fx=tp[x];
}
if(d[x]>d[y])swap(x,y);
if(id[x]!=id[y])
{
int tem=query(1,1,n,id[x]+1,id[y]);
if(a[ans].d<a[tem].d)ans=tem;
}
if(p==1)return a[ans].d;
else return ans;
}
int main()
{
freopen("tube.in","r",stdin);
freopen("tube.out","w",stdout);
n=read(),m=read(),q=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
insert(x,y,z);
dis[x][y]=dis[y][x]=z;
}
for(int i=1;i<=n;i++)rt[i]=i;
for(int i=1;i<=q;i++)
{
type[i]=read();
from[i]=read();
to[i]=read();
if(type[i]==2)ff[from[i]][to[i]]=ff[to[i]][from[i]]=1;//注意需要在type是2时 标记
}
kruskal();
d[1]=1;
dfs1(1);
dfs2(1,1);
build(1,1,n);
for(int i=q;i>0;i--)
{
if(type[i]==1)ans[i]=lca(from[i],to[i],1);
else
{
ff[from[i]][to[i]]=ff[to[i]][from[i]]=0;
int edge=lca(from[i],to[i],2);
if(dis[from[i]][to[i]]>=a[edge].d)continue;
a[mp[a[edge].t][a[edge].f]].t=-1;a[mp[a[edge].t][a[edge].f]].d=0;
a[mp[a[edge].f][a[edge].t]].t=-1;a[mp[a[edge].f][a[edge].t]].d=0;//把之前的边删去
add(from[i],to[i],dis[from[i]][to[i]]);
add(to[i],from[i],dis[from[i]][to[i]]);
mp[from[i]][to[i]]=len1-1;mp[to[i]][from[i]]=len1;
d[1]=1;cnt=0;
memset(fa,0,sizeof(fa));
memset(ra,0,sizeof(ra));
memset(son,0,sizeof(son));
memset(val,0,sizeof(val));
dfs1(1);
dfs2(1,1);
build(1,1,n);
}
}
for(int i=1;i<=q;i++)
if(type[i]==1)write(ans[i]);
//system("pause");
}