【zr25年省选联考day11】C. 图做题记录

给定一张 $n$ 个点 $m$ 条边的带边权有向图，对于 $u\in[2,n]$ ，求 $1$ 到 $u$ 的两条边不重复的路径的权值和的最小值，若不存在合法的两条路径则为 $-1$ 。

$1\le n\le 10^5$ ， $1\le m\le 2\times 10^5$ ，边权范围 $[0,10^9]$ 。

先建最短路树，设 $1$ 到 $u$ 的最短路为 $d_u$ 。

类比费用流的过程，对于点 $u$ ，其答案是 $d_u$ 加上：

反向 $u$ 到根的链上的边，并将这些边的边权乘 $-1$ 后 $1$ 到 $u$ 的最短路；

使用注意力，考虑负权边很难做，于是使用 Johnson 算法里的方法，将 $u\to v$ 的边权 $w$ 变为 $w'=w-d_v+d_u$ 。这样由于 $d_v\le d_u+w$ ，故有 $w'\ge 0$ ，而边权为 $w'$ 的最短路就是真实的最短路减去 $d_u$ 。

观察到对于边权为 $w$ 的树边 $u\to v$ ，有：

$w-d_v+d_u=0$ ；
$-w-d_u+d_v=0$ ；

所以无论树边有没有被反向，其 $w'$ 都为 $0$ 。

那么考虑反向且 $w\to w'$ 之后 $1$ 到 $u$ 的最短路，对于最短路上的一条非树边 $x\to y$ ，假设 $\text{lca}(x,y)=z$ ，那么上一次走非树边到达的点一定在链 $(x,y)$ 上：（注意树边边权都是 $0$ ）

使用人类智慧，我们尝试说明取消所有树边，并对于每条非树边 $x\to y$ 连 $(x,y)\to y$ 的权值不变的若干条边，即这样：（ $(x,y)$ 表示树上两点间的链）

注意到由于树边边权都是 $0$ 且有刚刚的结论，所以这样建边和原图是等价的。

具体的：

注意到 $u$ 相邻的树边没有指向 $u$ 的，所以 $u$ 一定是跳某条非树边 $x\to u$ 到达的；而根据刚刚的结论，上一次跳非树边一定是跳到 $(x,u)$ 中某个点的，故新图中存在直接相连的边；以此类推，这样建图不会变劣；
不难发现由于只会反向一条直链，所以不会出现新图中能到达而原图中不能到达的情况，而新图只是删掉了大量边权为 $0$ 的边，故不会变优；

这个形式就比较好做了，朴素的优化建图可以做到 $O(n\log^3n)$ 或者 $O(n\log^2n)$ 。

这里介绍一个 $O(n\log n)$ 的做法。该做法在 1984 年被 Tarjan 和 Suurballe 首次发表：A quick method for finding shortest pairs of disjoint paths。

考虑 dijkstra 的具体过程，每次我们会找到一个 $d_u$ 最小的点 $u$ 并松弛它的所有出边。而 $u$ 的出边对应的非树边一定从 $u$ 出发或者跨越了以 $u$ 为根时其两个不同儿子的子树。那么类似于点分治，每次将 $u$ 的联通块以 $u$ 为根，假设 $u$ 的儿子序列为 $a_{[1,k]}$ ，且子树大小为 $sz_{[1,k]}$ ，那么找到 $sz_i$ 最大的儿子 $i$ 并遍历 $u$ 除去 $i$ 外的所有儿子的子树进行松弛操作，然后删掉点 $i$ 。

比较两个儿子子树大小可以通过同时遍历子树来实现。

这样做每个点每次被遍历到其联通块大小都至少减半，故时间复杂度是 $O(n\log n)$ 。而每条非树边只会在 $\text{lca}$ 处造成一次入队，所以 dijkstra 的入队次数也是对的，所以总时间复杂度 $O(n\log n)$ 。

注意在访问邻边的时候需要将无用边删去，并且比较子树大小需要严格同时遍历（访问邻边也要同时进行），或者可以倍增比较（枚举 $k$ ，每次遍历超过 $2^k$ 个点就停止），否则时间复杂度不对。

代码如下：

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

typedef long long ll;

const int S=100005,MS=200005;
const ll inf=1e17;

int n,m;
vector<pair<pair<int,int>,int> > g1[S];
bool vis[S];
int prv[S],pid[S];
ll d[S];
bool del[MS];
vector<int> g[S];
vector<pair<pair<int,ll>,int> > g2[S];
int tx,ty;
pair<int,int> vx[S],vy[S];
int col[S];
priority_queue<pair<ll,int> > q;
ll dis[S];

inline void build()
{
	priority_queue<pair<ll,int> > q;
	for(int i=1;i<=n;i++) d[i]=inf;
	d[1]=0;
	q.emplace(-d[1],1);
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(auto t:g1[u])
		{
			int v=t.first.first,w=t.first.second,id=t.second;
			if(vis[v]||d[u]+w>=d[v]) continue;
			d[v]=d[u]+w;
			prv[v]=u,pid[v]=id;
			q.emplace(-d[v],v);
		}
	}
	for(int i=2;i<=n;i++)
	{
		if(d[i]==inf) continue;
		del[pid[i]]=true;
		g[prv[i]].push_back(i);
		g[i].push_back(prv[i]);
	}
}

void dfs(int u,int fa,int &sz)
{
	if(sz==0) return;
	sz--;
	for(int i=0;i<g[u].size();i++)
	{
		while(vis[g[u][i]])
		{
			swap(g[u][i],g[u].back());
			g[u].pop_back();
			if(i==g[u].size()) break;
		}
		if(i==g[u].size()) break;
		int v=g[u][i];
		if(v==fa) continue;
		dfs(v,u,sz);
		if(sz==0) break;
	}
}

bool cmp(int x,int y) // sz[x]>sz[y]
{
	for(int k=2;;k<<=1)
	{
		int ta=k,tb=k;
		dfs(x,0,ta),dfs(y,0,tb);
		if(ta>0||tb>0) return ta<=tb;
	}
}

void dfs1(int u,int fa,int c)
{
	col[u]=c;
	for(int i=0;i<g[u].size();i++)
	{
		while(vis[g[u][i]])
		{
			swap(g[u][i],g[u].back());
			g[u].pop_back();
			if(i==g[u].size()) break;
		}
		if(i==g[u].size()) break;
		int v=g[u][i];
		if(v==fa) continue;
		dfs1(v,u,c);
	}
}

void dfs2(int u,int fa,int rt)
{
	for(auto t:g2[u])
	{
		int v=t.first.first,id=t.second;
		ll w=t.first.second;
		if(del[id]||col[u]==col[v<0?-v:v]) continue;
		if(v<0) v=u;
		del[id]=true;
		if(dis[rt]+w<dis[v])
		{
			dis[v]=dis[rt]+w;
			q.emplace(-dis[v],v);
		}
	}
	for(int i=0;i<g[u].size();i++)
	{
		while(vis[g[u][i]])
		{
			swap(g[u][i],g[u].back());
			g[u].pop_back();
			if(i==g[u].size()) break;
		}
		if(i==g[u].size()) break;
		int v=g[u][i];
		if(v==fa) continue;
		dfs2(v,u,rt);
	}
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		g1[x].emplace_back(make_pair(y,w),i);
	}
	build();
	for(int i=1;i<=n;i++)
	{
		if(d[i]==inf) continue;
		for(auto t:g1[i])
		{
			if(del[t.second]) continue;
			int v=t.first.first,w=t.first.second;
			g2[i].emplace_back(make_pair(v,w-d[v]+d[i]),t.second);
			g2[v].emplace_back(make_pair(-i,w-d[v]+d[i]),t.second);
		}
	}
	int tc=0;
	for(int i=1;i<=n;i++) dis[i]=inf,vis[i]=false;
	dis[1]=0;
	q.emplace(-dis[1],1);
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(auto t:g2[u])
		{
			int v=t.first.first,id=t.second;
			ll w=t.first.second;
			if(del[id]||v<0) continue;
			del[id]=true;
			if(dis[u]+w<dis[v])
			{
				dis[v]=dis[u]+w;
				q.emplace(-dis[v],v);
			}
		}
		int ms=-1;
		for(int i=0;i<g[u].size();i++)
		{
			while(vis[g[u][i]])
			{
				swap(g[u][i],g[u].back());
				g[u].pop_back();
				if(i==g[u].size()) break;
			}
			if(i==g[u].size()) break;
			int v=g[u][i];
			if(ms==-1||cmp(v,ms)) ms=v;
		}
		for(int x:g[u])
		{
			if(x==ms) continue;
			dfs1(x,u,++tc);
		}
		for(int x:g[u])
		{
			if(x==ms) continue;
			dfs2(x,u,u);
		}
	}
	for(int i=2;i<=n;i++)
	{
		ll ans=d[i]*2+dis[i];
		if(ans>=inf) cout<<"-1\n";
		else cout<<ans<<'\n';
	}
	return 0;
}

【zr25年省选联考day11】C. 图 做题记录

感谢您的支持，我会继续努力的!

【zr25年省选联考day11】C. 图做题记录