noip2013day1-货车运输

题目描述

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

Input

第一行有两个用一个空格隔开的整数$n,m$，表示 $A $国有$n$ 座城市和 $m$ 条道路。

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

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

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

对于 $30\%$的数据，$0 < n < 1,000,0 < m < 10,000,0 < q< 1,000$；

对于 $60\%$的数据，$0 < n < 1,000,0 < m < 50,000,0 < q< 1,000$；

对于 $100\%$的数据，$0 < n < 10,000,0 < m < 50,000,0 < q< 30,000,0 ≤ z ≤ 100,000$。

Output

共有 $q$ 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出$−1$。

Sample Input

Sample Output

这个$q$的数据范围很显然是离线。。。

算法一：整体二分

仔细看题目，此题是要我们求出最大的$x-y$路径上的最小边权。

最大值最小，很显然可以二分答案。

把路径边权小于当前$mid$的边去掉，判断是否连通。

不过有那么多组数据一个个二分肯定很慢。

那么就可以用最巧妙的整体二分，把所有询问存下来，最后整体一起二分答案。

算法三：倍增

我们发现经过的路径一定是最大生成树上的边权。

因此，直接构造最大生成树，询问两个点时，实际上就是求$a-lca(a,b)$以及$b-lca(a,b)$路径上的最小值。

利用倍增维护即可。

算法二：启发式合并

此题是要我们求出最大的$x-y$路径上的最小边权。

我们先将所有询问的编号都丢到询问两边的点的$set$里面。

那我们就先把所有点都不建边，将所有边都存下来，再按边权由大到小排序，利用并查集维护连通。

将两个连通块连通时，我们同时将两个连通块的询问合并，这个过程可以利用启发式合并。

同时，若两个连通块的询问中有同一个编号，那么说明该询问这时被连通，更新答案即可。

代码如下

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define u64 unsigned long long

#define u32 unsigned int

#define reg register

#define Raed Read

#define debug(x) cerr<<#x<<" = "<<x<<endl;

#define rep(a,b,c) for(reg int a=(b),a##_end_=(c); a<=a##_end_; ++a)

#define ret(a,b,c) for(reg int a=(b),a##_end_=(c); a<a##_end_; ++a)

#define drep(a,b,c) for(reg int a=(b),a##_end_=(c); a>=a##_end_; --a)

#define erep(i,G,x) for(reg int i=(G).Head[x]; i; i=(G).Nxt[i])

inline int Read() {

	int res = 0, f = 1;

	char c;

	while (c = getchar(), c < 48 || c > 57)if (c == '-')f = 0;

	do res = (res << 3) + (res << 1) + (c ^ 48);

	while (c = getchar(), c >= 48 && c <= 57);

	return f ? res : -res;

}

template<class T>inline bool Min(T &a, T const&b) {

	return a > b ? a = b, 1 : 0;

}

template<class T>inline bool Max(T &a, T const&b) {

	return a < b ? a = b, 1 : 0;

}

const int N = 1e5+5,M = 2e5 + 5,mod = 99999997;

bool MOP1;

int n,m;

struct T360 {

	map<int,int>E[N],vis[N];

	struct node {

		int x,y,z;

	} Edge[500005];

	struct cmp {

		bool operator()(node a,node b)const {

			return a.z>b.z;

		}

	};

	int Ans[N];

	set<int>S[N];

	set<int>::iterator it;

	int Fa[N];

	int find(int x) {

		return Fa[x]==x?Fa[x]:Fa[x]=find(Fa[x]);

	}

	inline void solve(void) {

		int cnt=0;

		rep(i,1,m) {

			int x=Raed(),y=Read(),z=Read();

			Max(E[x][y],z);

			if(!vis[x][y])vis[x][y]=++cnt;

			Edge[vis[x][y]]=(node)<%x,y,E[x][y]%>;

		}

		sort(Edge+1,Edge+cnt+1,cmp());

		int q=Read();

		rep(i,1,q) {

			int x=Read(),y=Read();

			S[x].insert(i),S[y].insert(i);

		}

		memset(Ans,-1,sizeof Ans);

		rep(i,1,n)Fa[i]=i;

		rep(i,1,cnt) {

			int x=Edge[i].x,y=Edge[i].y,z=Edge[i].z;

			x=find(x),y=find(y);

			if(x==y)continue;

			if(S[x].size()<S[y].size())swap(x,y);

			for(it=S[y].begin(); it!=S[y].end(); it++) {

				int Now=*it;

				if(S[x].find(Now)==S[x].end())S[x].insert(Now);

				else Ans[Now]=z;

			}

			Fa[y]=x;

		}

		rep(i,1,q)printf("%lld\n",Ans[i]);

	}

} P60;

bool MOP2;

inline void _main(void) {

	n=Read(),m=Read();

	P60.solve();

}

signed main() {

#define offline1

#ifdef offline

	freopen("truck.in", "r", stdin);

	freopen("truck.out", "w", stdout);

	_main();

	fclose(stdin);

	fclose(stdout);

#else

	_main();

#endif

	return 0;

}

巴特西