[AMPPZ2014]Petrol

关键点的最小生成树？
关键点初始化为0，跑多源最短路，然后重构整个图，用Kruskal跑最小生成树
然后跑树链剖分在线回答询问
对树上每个点维护到链顶的最大值，结合线段树可以做到\(\Theta(n \log n)\)的复杂度
#include"cstdio"

#include"cstring"

#include"iostream"

#include"algorithm"

using namespace std;

const int MAXN=1<<18;

int n,m,s,np,root;

int x[MAXN],y[MAXN],z[MAXN],h[MAXN],c[MAXN],f[MAXN];

int blg[MAXN],hp[MAXN],id[MAXN],ln[MAXN],fa[MAXN],sn[MAXN];

int dep[MAXN],ren[MAXN],siz[MAXN],top[MAXN],val[MAXN],lis[MAXN];

int tree[MAXN<<1];

struct rpg{

	int li,nx,ln;

}a[MAXN<<1];

struct lint{

	int ls,nx,ln;

}line[MAXN];

inline int read()

{

	int x=0;char ch=getchar();

	while(ch<'0'||'9'<ch) ch=getchar();

	while('0'<=ch&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();

	return x;

}

void add(int ls,int nx,int ln)

{

	a[++np]=(rpg){h[ls],nx,ln};h[ls]=np;

	a[++np]=(rpg){h[nx],ls,ln};h[nx]=np;

}

void init()

{

	n=read(),s=read(),m=read();

	for(int i=1;i<=s;++i) c[i]=read();

	for(int i=1;i<=m;++i) x[i]=read(),y[i]=read(),z[i]=read(),add(x[i],y[i],z[i]);

	return;

}

void up(int x)

{

	for(int i=x,j=i>>1;j;i=j,j>>=1){

		if(ln[hp[i]]<ln[hp[j]]) swap(hp[i],hp[j]),swap(id[hp[i]],id[hp[j]]);

		else break;

	}return;

}

void ins(int x)

{

	hp[++hp[0]]=x;

	id[x]=hp[0];

	up(hp[0]);

	return;

}

void pop()

{

	id[hp[1]]=0;

	hp[1]=hp[hp[0]--];

	id[hp[1]]=1;

	for(int i=1,j=2;j<=hp[0];i=j,j<<=1){

		if(j<hp[0]&&ln[hp[j+1]]<ln[hp[j]]) ++j;

		if(ln[hp[i]]>ln[hp[j]]) swap(hp[i],hp[j]),swap(id[hp[i]],id[hp[j]]);

		else break;

	}return;

}

void SPkstra()

{

	memset(ln,0x7f,sizeof(ln));

	for(int i=1;i<=s;++i) ln[c[i]]=0,ins(c[i]),blg[c[i]]=c[i];

	while(hp[0]){

		int nw=hp[1];pop();

		for(int i=h[nw];i;i=a[i].li){

			if(ln[a[i].nx]>ln[nw]+a[i].ln){

				ln[a[i].nx]=ln[nw]+a[i].ln;

				blg[a[i].nx]=blg[nw];

				if(id[a[i].nx]) up(id[a[i].nx]);

				else ins(a[i].nx);

			}

		}

	}return;

}

bool cmp(lint a,lint b){return a.ln<b.ln;}

int find(int x){return f[x]==x?x:f[x]=find(f[x]);}

void un(int a,int b){int fa=find(a),fb=find(b);if(fa!=fb) f[fa]=fb;}

void Krusbuild()

{

	np=0;

	memset(a,0,sizeof(a));

	memset(h,0,sizeof(h));

	for(int i=1;i<=m;++i) line[i]=(lint){blg[x[i]],blg[y[i]],ln[x[i]]+ln[y[i]]+z[i]};

	for(int i=1;i<=n;++i) f[i]=i;

	sort(line+1,line+m+1,cmp);

	int ct=0;

	for(int i=1;i<=m;++i){

		if(find(line[i].ls)!=find(line[i].nx)){

			un(line[i].ls,line[i].nx);

			add(line[i].ls,line[i].nx,line[i].ln);

			++ct;

		}if(ct==s-1) break;

	}return;

}

void dfs1(int x,int f,int tp)

{

	fa[x]=f;

	dep[x]=tp;

	siz[x]=1;

	for(int i=h[x];i;i=a[i].li){

		if(a[i].nx==f) continue;

		dfs1(a[i].nx,x,tp+1);

		val[a[i].nx]=a[i].ln;

		siz[x]+=siz[a[i].nx];

		if(siz[sn[x]]<siz[a[i].nx]) sn[x]=a[i].nx;

	}return;

}

void dfs2(int x,int tpx,int v)

{

	id[x]=++id[0];

	ren[id[x]]=val[x];

	lis[x]=v;

	top[x]=tpx;

	if(!sn[x]) return;

	dfs2(sn[x],tpx,max(v,val[sn[x]]));

	for(int i=h[x];i;i=a[i].li){

		if(a[i].nx==fa[x]||a[i].nx==sn[x]) continue;

		dfs2(a[i].nx,a[i].nx,a[i].ln);

	}return;

}

void build(int k,int l,int r)

{

	if(l==r){

		tree[k]=ren[l];

		return;

	}int i=k<<1,mid=l+r>>1;

	build(i,l,mid);build(i|1,mid+1,r);

	tree[k]=max(tree[i],tree[i|1]);

	return;

}

void treecut()

{

	id[0]=0;

	for(int i=1;i<=s;++i) if(!dep[c[i]]) dfs1(c[i],c[i],1);

	for(int i=1;i<=s;++i) if(!id[c[i]]) dfs2(c[i],c[i],0);

	build(1,1,s);

	return;

}

int cask(int k,int l,int r,int le,int ri)

{

	if(le<=l&&r<=ri) return tree[k];

	int i=k<<1,mid=l+r>>1,maxn=0;

	if(le<=mid) maxn=max(maxn,cask(i,l,mid,le,ri));

	if(mid<ri) maxn=max(maxn,cask(i|1,mid+1,r,le,ri));

	return maxn;

}

int qmax(int x,int y)

{

	int maxn=0;

	while(top[x]!=top[y]){

		if(dep[top[x]]<dep[top[y]]) swap(x,y);

		maxn=max(maxn,lis[x]);

		x=fa[top[x]];

	}if(dep[x]>dep[y]) swap(x,y);

	if(id[x]+1<=id[y]) maxn=max(maxn,cask(1,1,s,id[x]+1,id[y]));

	return maxn;

}

void solve()

{

	m=read();

	while(m--){

		int x=read(),y=read(),d=read();

		if(find(x)!=find(y)||qmax(x,y)>d) puts("NIE");

		else puts("TAK");

	}return;

}

int main()

{

	init();

	SPkstra();

	Krusbuild();

	treecut();

	solve();

	return 0;

}
巴特西

[AMPPZ2014]Petrol

最新文章

热门文章
