[Noip 2013 Day1-3] 货车运输做法总结

Online Judge：Luogu-1967

Label：启发式合并，离线，整体二分，按秩合并，倍增，最大生成树

打模拟离线赛时做到，顺便总结一下。

一、启发式合并

离线询问，将询问存在端点上。将每条边按照权值从大到小排列。

依照刚才的顺序依次连上这m条边，利用并查集维护图的连通性。合并时采用启发式合并的思维——将所含元素较小的集合连上较大的集合。对于那个较小的集合，我们直接暴力遍历其中的每个点，再暴力回答那个节点上的询问。

总的时间复杂度为(O(NlogN))，由于暴力枚举，常数可能会较大。

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,m,ans[30010],fa[N];
inline int read(){}
struct node{
	int u,v,d;
};
vector<node>e;
struct ques{
	int to,id;
};
vector<ques>Q[N];
inline bool cmp(node a,node b){
	return a.d>b.d;
}
vector<int>son[N];
int find(int x){return x==fa[x]?x:find(fa[x]);}
bool ff;
int main(){
//	cout<<(&ff-&f)/1024/1024<<endl;
//	freopen("truck.in","r",stdin),freopen("truck.out","w",stdout);
	n=read(),m=read();
	for(register int i=1;i<=n;++i)fa[i]=i,son[i].push_back(i);
	int ma=0;
	for(int i=1;i<=m;++i){
		int u=read(),v=read(),d=read();
		e.push_back((node){u,v,d});
		if(d>ma)ma=d;
	}
	sort(e.begin(),e.end(),cmp);
	int q=read();
	for(register int i=1;i<=q;++i){
		int st=read(),ed=read();
		Q[st].push_back((ques){ed,i});
		Q[ed].push_back((ques){st,i});
		ans[i]=-1;
	}
	for(int j=0;j<e.size();j++){
		int u=e[j].u,v=e[j].v,d=e[j].d;
		int A=find(u),B=find(v);
		if(A==B)continue;
		if(son[A].size()>son[B].size())swap(A,B);
		fa[A]=B;	
		for(int i=0;i<son[A].size();++i){
			int x=son[A][i];
			for(int j=0;j<Q[x].size();j++){
				if(~ans[Q[x][j].id])continue;
				if(find(x)==find(Q[x][j].to))ans[Q[x][j].id]=d;
			}
			son[B].push_back(x);
		}
		son[A].clear();	
	}
	for(register int i=1;i<=q;++i)printf("%d
",ans[i]);
}

二、最大生成树+倍增

为了方便表述，令(u->v)路径上，所有边权的最小值最大为(lim(u,v))，其实就是题目中的询问。

很自然想到重构一棵树，依据刚才的分析，很明显是构造棵最大生成树。最大生成树的写法跟最小生成树的写法一模一样，把边从大到小排序即可。

接下来的询问就是围绕这棵树展开了。

求(lim(u,v))?有点像求树上两点间距离的亚子。联想倍增求LCA的过程，对于(lim(u,v))我们是不是也可以通过倍增维护呢？

定义(w[i][j])表示从(i)这个点向上(2^j)条边的边权最小值。维护过程跟倍增求LCA维护那个(fa[i][j])数组几乎一样，注意点细节即可。

预处理完(w)数组之后，就模拟求LCA的过程，然后顺便算出(lim(u,v))即可。这个做法思路比较顺畅，但实现时注意细节。

#include<bits/stdc++.h>
using namespace std;
const int N=10009;
const int INF=100009;
int bcj[N],fa[N][16],dep[N],vis[N],w[N][16];
int n,m;
struct node{
	int u,v,w;
};
vector<node>e;
struct edge{
	int to,w;
};
vector<edge>g[N];
inline bool cmp(node a,node b){return a.w>b.w;}
int find(int x){return x==bcj[x]?x:bcj[x]=find(bcj[x]);}
void Buildtree(){
	sort(e.begin(),e.end(),cmp);
	for(int i=1;i<=n;i++)bcj[i]=i;
	for(int i=0;i<e.size();i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		int A=find(u),B=find(v);
		if(A==B)continue;
		bcj[A]=B;
		g[u].push_back((edge){v,w});
		g[v].push_back((edge){u,w});
	}
} 
void dfs(int x,int d){
	vis[x]=1,dep[x]=d;
	for(int i=0;i<g[x].size();i++){
		int y=g[x][i].to;if(vis[y])continue;
		fa[y][0]=x;w[y][0]=g[x][i].w;
		dfs(y,d+1);
	}
}
int LCA(int a,int b){//其实返回的是u到v的路径中，w的最小值
	if(find(a)!=find(b))return -1;
	if(dep[a]>dep[b])swap(a,b);
	int step=dep[b]-dep[a],res=INF;
	for(int i=0;i<=15;i++){
		if(step&(1<<i))res=min(res,w[b][i]),b=fa[b][i];
	}
	if(a==b)return res;
	for(int i=15;i>=0;i--){
		if(fa[a][i]!=fa[b][i]){
			res=min(res,w[a][i]);
			res=min(res,w[b][i]);
			a=fa[a][i],b=fa[b][i];
		}
	}
	res=min(res,w[a][0]);
	res=min(res,w[b][0]);
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		e.push_back((node){u,v,w});
	}
	Buildtree();
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			w[i][0]=INF;fa[i][0]=0;
			dfs(i,0);
		}
	}	
	for(int j=1;j<=15;j++)for(int i=1;i<=n;i++){
		fa[i][j]=fa[fa[i][j-1]][j-1];
		w[i][j]=min(w[i][j-1],w[fa[i][j-1]][j-1]);
	}
	int q;scanf("%d",&q);
	while(q--){
		int u,v;scanf("%d%d",&u,&v);
		printf("%d
",LCA(u,v));
	}	
}

三、整体二分

ps:整体二分的模板题还有求区间第k大。

对于60%的数据：

我们有一种很low的做法，就是对于每个询问，都去(O(logZ))(Z为图中最大的边权)的二分查找那个两点间边权最小值的最大值——这很明显是二分查找题目的一种套路常见问法。

然后再用(O(N))的时间暴搜一遍check一下。最终时间复杂度为(O(Q*logZ*N))。

优化：

发现询问数很大，上面那样做会TLE。考虑将所有询问一起二分，这样复杂度就变成了(O(logZ*N))，但是常数可能会因为一些奇奇怪怪的操作而变得有点大。

看代码会比较好理解233：

#include<bits/stdc++.h>
using namespace std;
const int N=10009,INF=100000;
int n,m,qnum,res[30010];
struct edge{int u,v,w;}e[50010];
inline bool edgecmp(edge a,edge b){return a.w>b.w;}
struct node{
	int u,v;
	int l,r,mid,id,ans;
}q[30010];
inline bool querycmp(node a,node b){return a.mid>b.mid;}

int fa[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void init(){for(int i=1;i<=n;i++)fa[i]=i;}
void merge(int a,int b){
	int A=find(a),B=find(b);
	if(A!=B)fa[A]=B;
}

void Global_Search(){
	sort(e+1,e+m+1,edgecmp);
	int times=20;//log2(INF)
	while(times--){
		int cur=1;
		sort(q+1,q+qnum+1,querycmp);
		init();
		for(int i=1;i<=qnum;i++){
			if(q[i].l>q[i].r)continue;
			while(cur<=m&&e[cur].w>=q[i].mid){
				merge(e[cur].u,e[cur].v);cur++;
			}
			int qu=q[i].u,qv=q[i].v;
			int A=find(qu),B=find(qv);
			if(A==B){q[i].l=q[i].mid+1,q[i].ans=q[i].mid;}
			else q[i].r=q[i].mid-1;
			q[i].mid=(q[i].l+q[i].r)>>1;
		}	
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		e[i]=((edge){u,v,w}); 
	}
	scanf("%d",&qnum);
	for(int i=1;i<=qnum;i++){
		scanf("%d%d",&q[i].u,&q[i].v);
		q[i].l=0,q[i].r=INF,q[i].mid=(0+INF)>>1;
		q[i].id=i;q[i].ans=-1;
	}
	Global_Search();
	for(int i=1;i<=qnum;i++)res[q[i].id]=q[i].ans;
	for(int i=1;i<=qnum;i++)printf("%d
",res[i]);
}

此题还可以按秩合并，做法与前面几种类似，就不赘述勒。。