题目描述

A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。

输入输出格式

输入格式:

输入文件名为 truck.in。

输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道

路。 接下来 m 行每行 3 个整数 x、 y、 z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意: x 不等于 y,两座城市之间可能有多条道路 

接下来一行有一个整数 q,表示有 q 辆货车需要运货。

接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货物到 y 城市,注意: x 不等于 y 

输出格式:

输出文件名为 truck.out。

输出共有 q 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货

车不能到达目的地,输出-1。

先Kruskal跑一下最大生成树,就是把边权改成从大到小排序就行。

然后用倍增思想在有根树上记录一个minp[i][k]数组,表示这个点i上跳2k的高度,经过路径的最小边权:

	minp[nownode][0]=tree[nownode].w;
	for (register int i=1;i<=25;i++) 
	{
		l[nownode][i]=l[l[nownode][i-1]][i-1];
		minp[nownode][i]=minx(minp[nownode][i-1],minp[l[nownode][i-1]][i-1]);
	}

显然它等于minp[i][k-1]和minp[l[i][k-1][k-1]中的最小值。也就是它向上跳2k-1高度的minp和从depth[i]-2k-1高度再往上跳2k-1高度的minp(参照倍增的思想)

而向上跳2k-1高度能够达到点l[i][k-1],这个就属于LCA的基本操作了吧……

注意初始化。

还要维护一下点的联通行……用Kruskal留下来的UFS就行。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;

//graph
struct ed
{
	int pre,to,w;
}edge[100010]={0};
int nodenum,edgenum,pointer[10010]={0},at=1,fx,tx,wx;
//minimal spanning tree
struct edk
{
	int from,to,w;
}edge_k[200010]={0};
int fatherx[10010]={0};
//tree
struct tr
{
	int father,depth,w;
}tree[10010]={0};
int l[10010][30]={0},minp[10010][30]={0};
//test
int cachev,cacheu,uvlca,qnum;

inline void readx(int& x)
{
	register char ch=0; x=0;
	while (ch<'0' || ch>'9') ch=getchar();
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
}
bool cmp(edk a,edk b) { return a.w>b.w; }
inline int minx(int a,int b) { if (a<b) b=a; return b; }
inline void Insert()
{
	edge[at].pre=pointer[fx];
	edge[at].to=tx;
	edge[at].w=wx;
	pointer[fx]=at;
	at++;
	edge[at].pre=pointer[tx];
	edge[at].to=fx;
	edge[at].w=wx;
	pointer[tx]=at;
	at++;
}

int findx(int e)
{
	if (fatherx[e]!=e) fatherx[e]=findx(fatherx[e]);
	return fatherx[e];
}
inline void mergex(int a,int b) { fatherx[findx(b)]=fatherx[a]; }

inline void kruskal()
{
	int c1=0;
	for (register int i=1;i<=nodenum;i++) fatherx[i]=i;
	sort(edge_k+1,edge_k+edgenum+1,cmp);
	for (register int i=1;i<=edgenum;i++)
	{
		if (findx(edge_k[i].from)!=findx(edge_k[i].to))
		{
			mergex(edge_k[i].from,edge_k[i].to);
			fx=edge_k[i].from;
			tx=edge_k[i].to;
			wx=edge_k[i].w;
			Insert();
			c1++;
			if (c1==(nodenum-1)) break;
		}
	}
}

void build(int nownode)
{
	l[nownode][0]=tree[nownode].father;
	minp[nownode][0]=tree[nownode].w;
	for (register int i=1;i<=25;i++) 
	{
		l[nownode][i]=l[l[nownode][i-1]][i-1];
		minp[nownode][i]=minx(minp[nownode][i-1],minp[l[nownode][i-1]][i-1]);
	}
	
	register int prex=pointer[nownode];
	while (prex)
	{
		if (!(edge[prex].to==tree[nownode].father))
		{
			tree[edge[prex].to].father=nownode;
			tree[edge[prex].to].depth=tree[nownode].depth+1;
			tree[edge[prex].to].w=edge[prex].w;
			build(edge[prex].to);
		}
		prex=edge[prex].pre;
	}
}

inline void buildtree()
{
	memset(minp,0x3f,sizeof(minp));
	for (register int i=1;i<=nodenum;i++)
	{
		if (fatherx[i]==i)
		{
			tree[i].w=1e9;
			tree[i].depth=1;
			build(i);
		}
	}
}

inline int LCA(register int u,register int v)
{
	int getx=1e9;
	for (register int i=18;i>=0;i--) if (tree[l[u][i]].depth>=tree[v].depth) 
	{
		getx=minx(getx,minp[u][i]);
		u=l[u][i];
	}
	if (u==v) return getx;
	
	for (register int i=18;i>=0;i--) if (l[u][i]!=l[v][i])
	{	
		getx=minx(getx,minp[u][i]);
		getx=minx(getx,minp[v][i]);
		u=l[u][i]; v=l[v][i];
	}
	getx=minx(getx,minp[u][0]);
	getx=minx(getx,minp[v][0]);
	return getx;	
}

int main()
{
	readx(nodenum); readx(edgenum);
	for (register  int i=1;i<=edgenum;i++) { readx(edge_k[i].from); readx(edge_k[i].to); readx(edge_k[i].w); }
	
	kruskal();
	buildtree();
	
	readx(qnum);
	for (register int i=1;i<=qnum;i++)
	{
		readx(cacheu); readx(cachev);
		if (findx(cacheu)!=findx(cachev)) printf("-1\n");
		else
		{
			if (tree[cacheu].depth<tree[cachev].depth) swap(cacheu,cachev);
			printf("%d\n",LCA(cacheu,cachev));
		}
	}
	
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注