【BZOJ4912】天才黑客（最短路，虚树）

题面

题解

\(Anson\)爷讲过的题目，然而我还是不会做

只有照着\(zsy\)的程序打我才会做。。。。果然太弱了。

这道题目显然是把边看成点，然后把原图中的每一个点的入边和出边之间相互连边，

边权是\(lcp\)的长度，也就是在\(Trie\)树上对应的点的\(LCA\)

那么，考虑如何优化，对于一个点，把它的入边和出现对应的按照\(dfs\)序排序

利用虚树的思想，此时只需要相邻的点求\(LCA\)

那么，对于一个\(LCA\)，显然可以把建立一个虚点，把它的所有儿子全部连上来，

因为儿子可能在之前就连在某个虚点上了，这样子只需要把虚点连上来就好了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 111111

#define MAXL 1111111

#define pi pair<int,int>

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int n,m,k,V[MAXL],h1[MAX],h2[MAX],Cnt,pos[MAXL];

struct Line{int v,next;}e[MAX];

inline void Add(int *h,int u,int v){e[++Cnt]=(Line){v,h[u]};h[u]=Cnt;}

struct Trie

{

	struct Line{int v,next;}e[MAX];

	int h[MAX],cnt;

	inline void Add(int u,int v){e[++cnt]=(Line){v,h[u]};h[u]=cnt;}

	int dfn[MAX],st[18][MAX],lg[MAX],tim,dep[MAX];

	void init(){memset(h,0,sizeof(h));tim=cnt=0;memset(st,0,sizeof(st));}

	void dfs(int u)

	{

		st[0][dfn[u]=++tim]=dep[u];

		for(int i=h[u];i;i=e[i].next)

			dep[e[i].v]=dep[u]+1,dfs(e[i].v),st[0][++tim]=dep[u];

	}

	void pre()

	{

		dfs(1);

		for(int i=2;i<=tim;++i)lg[i]=lg[i>>1]+1;

		for(int j=1;j<=lg[tim];++j)

			for(int i=1;i+(1<<j)-1<=tim;++i)

				st[j][i]=min(st[j-1][i],st[j-1][i+(1<<(j-1))]);

	}

	int LCA(int u,int v)

	{

		u=dfn[u];v=dfn[v];if(u>v)swap(u,v);

		int k=lg[v-u+1];

		return min(st[k][u],st[k][v-(1<<k)+1]);

	}

}T;

struct Graph

{

	struct Line{int v,next,w;}E[MAXL];

	int h[MAXL],cnt,tot;bool vis[MAXL];

	inline void Add(int u,int v,int w){E[++cnt]=(Line){v,h[u],w};h[u]=cnt;}

	void init(){memset(h,0,sizeof(h));memset(vis,0,sizeof(vis));cnt=0;}

	int dis[MAXL];

	void Dijkstra()

	{

		priority_queue<pi,vector<pi>,greater<pi> >Q;

		memset(dis,127,sizeof(dis));

		for(int i=h1[1];i;i=e[i].next)

			Q.push(make_pair(dis[e[i].v]=V[e[i].v],e[i].v));

		while(!Q.empty())

		{

			int u=Q.top().second;Q.pop();

			if(vis[u])continue;vis[u]=true;

			for(int i=h[u];i;i=E[i].next)

			{

				int v=E[i].v;

				if(dis[v]>dis[u]+E[i].w+V[v])

					dis[v]=dis[u]+E[i].w+V[v],Q.push(make_pair(dis[v],v));

			}

		}

	}

}G;

int S[MAX],top,p1[MAX],p2[MAX],q1[MAX],q2[MAX];

bool cmp(int a,int b){return T.dfn[pos[abs(a)]]<T.dfn[pos[abs(b)]];}

void Link(int u)

{

	top=0;

	for(int i=h2[u];i;i=e[i].next)S[++top]=e[i].v;

	for(int i=h1[u];i;i=e[i].next)S[++top]=-e[i].v;

	sort(&S[1],&S[top+1],cmp);

	for(int i=1;i<=top;++i)

	{

		p1[i]=++G.tot;p2[i]=++G.tot;q1[i]=++G.tot;q2[i]=++G.tot;

		if(i>1)

		{

			G.Add(p1[i-1],p1[i],0);G.Add(q1[i-1],q1[i],0);

			G.Add(p2[i],p2[i-1],0);G.Add(q2[i],q2[i-1],0);

		}

		if(S[i]>0)G.Add(S[i],p1[i],0),G.Add(S[i],p2[i],0);

		else S[i]=-S[i],G.Add(q1[i],S[i],0),G.Add(q2[i],S[i],0);

	}

	for(int i=1;i<top;++i)

	{

		int u=T.LCA(pos[S[i]],pos[S[i+1]]);

		G.Add(p1[i],q1[i+1],u);G.Add(p2[i+1],q2[i],u);

	}

}

int main()

{

	int Cases=read();

	while(Cases--)

	{

		n=read();m=G.tot=read();k=read();Cnt=0;

		G.init();T.init();memset(V,0,sizeof(V));

		memset(h1,0,sizeof(h1));memset(h2,0,sizeof(h2));

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

		{

			int u=read(),v=read();V[i]=read();pos[i]=read();

			Add(h1,u,i);Add(h2,v,i);

		}

		for(int i=1;i<k;++i){int u=read(),v=read(),w=read();T.Add(u,v);}

		T.pre();

		for(int i=2;i<=n;++i)Link(i);

		G.Dijkstra();

		for(int u=2;u<=n;++u)

		{

			int ans=2e9;

			for(int i=h2[u];i;i=e[i].next)

				ans=min(ans,G.dis[e[i].v]);

			printf("%d\n",ans);

		}

	}

	return 0;

}

巴特西

【BZOJ4912】天才黑客（最短路，虚树）

【BZOJ4912】天才黑客（最短路，虚树）

题面

题解

最新文章

热门文章