BZOJ4912 SDOI2017天才黑客（最短路+虚树）

比眉伴天荒 2021-09-29 20:10 263阅读 0赞

容易想到把边当成点重建图跑最短路。将每条边拆成入边和出边，作为新图中的两个点，由出边向入边连边权为原费用的边。对于原图中的每个点，考虑由其入边向出边连边。直接暴力两两连边当然会被卡掉，注意到其边权是trie上lca的深度，由lca转rmq的做法可知，两点lca即为欧拉序区间中它们之间深度最小的点，于是跑出欧拉序后对入边出边的前后缀建虚点连边即可。当然每次连边时都需要将trie上有用的点提取出来，建虚树即可。

#include<iostream> 
    #include<cstdio>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    #include<queue>
    using namespace std;
    #define ll long long
    #define N 50010
    #define inf 2000000000
    #define in(i) (i*2+n)
    #define out(i) (i*2+n-1)
    char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
    int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
    int read()
    {
    	int x=0,f=1;char c=getchar();
    	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    	return x*f;
    }
    int T,n,m,k,p[N],t;
    struct data{int to,nxt,len,s;
    }edge[N];
    vector<int> in_edge[N];
    namespace trie
    {
    	int p[N],t,fa[N][18],deep[N],dfn[N],cnt;
    	struct data{int to,nxt;}edge[N];
    	void clear(){memset(p,0,sizeof(p));cnt=t=0;}
    	void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}
    	void dfs(int k)
    	{
    		dfn[k]=++cnt;
    		for (int i=p[k];i;i=edge[i].nxt)
    		{
    			deep[edge[i].to]=deep[k]+1;
    			fa[edge[i].to][0]=k;
    			dfs(edge[i].to);
    		}
    	}
    	void build()
    	{
    		fa[1][0]=1;dfs(1);
    		for (int j=1;j<18;j++)
    			for (int i=1;i<=k;i++)
    			fa[i][j]=fa[fa[i][j-1]][j-1];
    	}
    	int lca(int x,int y)
    	{
    		if (deep[x]<deep[y]) swap(x,y);
    		for (int j=17;~j;j--) if (deep[fa[x][j]]>=deep[y]) x=fa[x][j];
    		if (x==y) return x;
    		for (int j=17;~j;j--) if (fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];
    		return fa[x][0];
    	}
    }
    namespace graph
    {
    	int p[N<<6],t,cnt,dis[N<<6];
    	bool flag[N<<6];
    	struct data{int to,nxt,len;}edge[N<<7];
    	struct data2
    	{
    		int x,d;
    		bool operator <(const data2&a) const
    		{
    			return d>a.d;
    		}
    	};
    	priority_queue<data2> q;
    	void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}
    	void clear(){cnt=n+m*2;t=0;memset(p,0,sizeof(p));}
    	void dijkstra()
    	{
    		for (int i=1;i<=cnt;i++) dis[i]=inf;dis[1]=0;
    		memset(flag,0,sizeof(flag));
    		q.push((data2){1,0});
    		for (;;)
    		{
    			while (!q.empty()&&flag[q.top().x]) q.pop();
    			if (q.empty()) break;
    			data2 x=q.top();q.pop();
    			flag[x.x]=1;
    			for (int i=p[x.x];i;i=edge[i].nxt)
    			if (dis[x.x]+edge[i].len<dis[edge[i].to])
    			{
    				dis[edge[i].to]=dis[x.x]+edge[i].len;
    				q.push((data2){edge[i].to,dis[edge[i].to]});
    			}
    		}
    	}
    }
    namespace virtual_tree
    {
    	int a[N],tot,stk[N],id[N<<1],top,p[N],x[N],y[N],idin[N<<1],idout[N<<1],pre[N<<1],suf[N<<1],t,cnt;
    	struct data{int to,nxt;}edge[N<<1];
    	void addedge(int u,int v){t++;x[t]=u,y[t]=v;}
    	void clear(){tot=top=t=cnt=0;}
    	void push(int x){a[++tot]=x;}
    	bool cmp(const int&a,const int&b)
    	{
    		return trie::dfn[a]<trie::dfn[b];
    	}
    	void dfs(int k)
    	{
    		id[++cnt]=k;idin[k]=graph::cnt+cnt;
    		for (int i=p[k];i;i=edge[i].nxt)
    		{
    			dfs(edge[i].to);
    			id[++cnt]=k;
    		}
    	}
    	void build()
    	{
    		if (tot==0) return;
    		sort(a+1,a+tot+1,cmp);
    		tot=unique(a+1,a+tot+1)-a-1;
    		stk[++top]=1;
    		for (int i=1+(a[1]==1);i<=tot;i++)
    		{
    			int l=trie::lca(a[i],stk[top]);
    			if (stk[top]!=l)
    			{
    				while (top>1&&trie::deep[stk[top-1]]>=trie::deep[l]) addedge(stk[top-1],stk[top]),top--;
    				if (stk[top]!=l) addedge(l,stk[top]);
    				stk[top]=l;
    			}
    			stk[++top]=a[i];
    		}
    		while (top>1) addedge(stk[top-1],stk[top]),top--;
    		for (int i=1;i<=t;i++) p[x[i]]=p[y[i]]=0;
    		for (int i=1;i<=t;i++) edge[i].to=y[i],edge[i].nxt=p[x[i]],p[x[i]]=i;
    		dfs(1);for (int i=1;i<=cnt;i++) idout[id[i]]=idin[id[i]]+cnt;graph::cnt+=cnt<<1;
    		for (int i=1;i<=cnt;i++)
    		{
    			pre[i]=++graph::cnt;
    			graph::addedge(idin[id[i]],pre[i],0);
    			if (i>1) graph::addedge(pre[i-1],pre[i],0);
    		}
    		for (int i=cnt;i>=1;i--)
    		{
    			suf[i]=++graph::cnt;
    			graph::addedge(suf[i],idout[id[i]],0);
    			if (i<cnt) graph::addedge(suf[i],suf[i+1],0);
    		}
    		for (int i=1;i<=cnt;i++) graph::addedge(pre[i],suf[i],trie::deep[id[i]]);
    		for (int i=1;i<=cnt;i++)
    		{
    			pre[i]=++graph::cnt;
    			graph::addedge(pre[i],idout[id[i]],0);
    			if (i>1) graph::addedge(pre[i],pre[i-1],0);
    		}
    		for (int i=cnt;i>=1;i--)
    		{
    			suf[i]=++graph::cnt;
    			graph::addedge(idin[id[i]],suf[i],0);
    			if (i<cnt) graph::addedge(suf[i+1],suf[i],0);
    		}
    		for (int i=1;i<=cnt;i++) graph::addedge(suf[i],pre[i],trie::deep[id[i]]);
    	}
    }
    int main()
    {
    #ifndef ONLINE_JUDGE
    	freopen("bzoj4912.in","r",stdin);
    	freopen("bzoj4912.out","w",stdout);
    	const char LL[]="%I64d\n";
    #else
    	const char LL[]="%lld\n";
    #endif
    	T=read();
    	while (T--)
    	{
    		n=read(),m=read(),k=read();
    		memset(p,0,sizeof(p));t=0;
    		for (int i=1;i<=n;i++) in_edge[i].clear();
    		for (int i=1;i<=m;i++)
    		{
    			int x=read(),y=read(),len=read(),s=read();
    			t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=len,edge[t].s=s,p[x]=t;
    		}
    		trie::clear();
    		for (int i=1;i<k;i++)
    		{
    			int x=read(),y=read(),z=read();
    			trie::addedge(x,y);
    		}
    		trie::build();
    		graph::clear();
    		for (int i=p[1];i;i=edge[i].nxt)
    		graph::addedge(1,out(i),0);
    		for (int i=1;i<=m;i++) if (edge[i].to!=1) graph::addedge(in(i),edge[i].to,0);
    		for (int i=1;i<=m;i++) graph::addedge(out(i),in(i),edge[i].len);
    		for (int i=1;i<=m;i++) in_edge[edge[i].to].push_back(i);
    		for (int i=1;i<=n;i++)
    		{
    			virtual_tree::clear();
    			for (int j=0;j<in_edge[i].size();j++) virtual_tree::push(edge[in_edge[i][j]].s);
    			for (int j=p[i];j;j=edge[j].nxt) virtual_tree::push(edge[j].s);
    			virtual_tree::build();
    			for (int j=0;j<in_edge[i].size();j++) graph::addedge(in(in_edge[i][j]),virtual_tree::idin[edge[in_edge[i][j]].s],0);
    			for (int j=p[i];j;j=edge[j].nxt) graph::addedge(virtual_tree::idout[edge[j].s],out(j),0);
    		}
    		graph::dijkstra();
    		for (int i=2;i<=n;i++) printf("%d\n",graph::dis[i]);
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/Gloid/p/10347036.html