记录编号	107	评测结果	AWWWTTTTTT
题目名称	[WC 2006] 水管局长	最终得分	10
用户昵称	BYVoid	是否通过	未通过
代码语言	C++	运行时间	20.125 s
提交时间	2008-04-22 17:48:45	内存使用	11.53 MiB

#include <iostream>
#include <fstream>
#define MAXN 1001
#define MAXM 100001
#define MAXQ 100001

using namespace std;

class ufs
{
public:
	long *father;
	long n;
	long find(long k)
	{
		long F,e=k,t;
		while (father[e]>0) e=father[e];
		F=e;
		e=k;
		while (father[e]>0)
		{
			t=e;
			e=father[e];
			father[t]=F;
		}

		return e;
	}
	ufs(long a)
	{
		long i;
		n=a;
		father=(long *)malloc((n+1)*sizeof(long));
		for (i=1;i<=n;i++)
			father[i]=-i;
	}	
	bool judge(long a,long b)
	{
		return father[find(a)]==father[find(b)];
	}
	void uni(long a,long b)
	{
		father[find(b)]=find(a);
	}
};

typedef struct
{
	long a,b,v;
}edge;

ifstream fi("tube.in");
ofstream fo("tube.out");

long N,M,Q,ITF;
edge E[MAXM],Req[MAXM],maxE;
long dis[MAXN][MAXN];
long adjl[MAXN][MAXN];
long ans[MAXQ],acnt;
bool deleted[MAXN][MAXN];
ufs *U;

inline int cmp(const void * a,const void * b)
{
	return ((edge*)a)->v<((edge*)b)->v?-1:1;
}

void init()
{
	long i;
	fi >> N >> M >> Q;
	memset(dis,0xf,sizeof(dis));
	ITF=dis[0][0];
	for (i=1;i<=N;i++)
		dis[i][i]=0;
	for (i=1;i<=M;i++)
	{
		long a,b,v;
		fi >> a >> b >> v;
		E[i].a=a;
		E[i].b=b;
		E[i].v=v;
		dis[a][b]=dis[b][a]=v;
	}
	U=new ufs(N);
	qsort(E+1,M,sizeof(edge),cmp);
}

inline long max(long a,long b)
{
	return a>b?a:b;
}

inline long min(long a,long b)
{
	return a<b?a:b;
}

void kruskal()
{
	memset(dis,0,sizeof(dis));
	long cnt=0,i;
	edge slv;
	for (i=1;i<=M;i++)
	{
		slv=E[i];
		if (deleted[slv.a][slv.b]) continue;
		if (!U->judge(slv.a,slv.b))
		{
			U->uni(slv.a,slv.b);
			dis[slv.a][slv.b]=dis[slv.b][slv.a]=slv.v;
			adjl[slv.a][ ++adjl[slv.a][0] ]=slv.b;
			adjl[slv.b][ ++adjl[slv.b][0] ]=slv.a;
			cnt++;
		}
		if (cnt==N-1)
			break;
	}
}

bool findcircle(long c,long from,long S)
{
	long i,j;
	for (i=1;i<=adjl[c][0];i++)
	{
		j=adjl[c][i];
		if (dis[c][j]==ITF) continue;
		if (j==from) continue;
		if (j==S)
			return true;
		bool b=findcircle(j,c,S);
		if (b)
		{
			if (dis[c][j]>maxE.v)
			{
				maxE.a=c;
				maxE.b=j;
				maxE.v=dis[c][j];
			}
			return true;
		}
	}
	return false;
}

void deleteedge(edge e)
{
	dis[e.a][e.b]=dis[e.b][e.a]=ITF;
}

void addedge(edge e)
{
	maxE.v=0;

	adjl[e.a][ ++adjl[e.a][0] ]=e.b;
	adjl[e.b][ ++adjl[e.b][0] ]=e.a;
	dis[e.a][e.b]=dis[e.b][e.a]=e.v;

	findcircle(e.a,0,e.a); //查找环中权值最大边

	deleteedge(maxE);//删除权值最大边
}

long get(long c,long from,long S)
{
	long i,j;
	for (i=1;i<=adjl[c][0];i++)
	{
		j=adjl[c][i];
		if (dis[c][j]==ITF) continue;
		if (j==from) continue;
		if (j==S)
			return dis[c][j];
		long b=get(j,c,S);
		if (b!=-1)
		{
			return max(b,dis[c][j]);
		}
	}
	return -1;
}

void request()
{
	long i;
	for (i=Q;i>=1;--i)
	{
		if (Req[i].v<0)//添加边
		{
			Req[i].v=-Req[i].v;
			addedge(Req[i]);
		}
		else //查找
		{
			ans[++acnt]=get(Req[i].a,0,Req[i].b);
		}
	}
}

void print()
{
	long i;
	for (i=acnt;i>=1;i--)
		fo << ans[i]  <<endl;
	fi.close();
	fo.close();
}

void deleteedge()
{
	long q,k,x,y;
	for (q=1;q<=Q;q++)
	{
		fi >> k >> x >> y;
		Req[q].a=x;
		Req[q].b=y;
		Req[q].v=dis[x][y];
		if (k==2) //添加边
		{
			Req[q].v=-Req[q].v;
			deleted[x][y]=deleted[y][x]=true;
		}
	}
}

int main()
{
	init();
	deleteedge();
	kruskal();
	request();
	print();
	return 0;
}