\(\mathcal{Description}\)

link.

给定 \(n\) 个点 \(m\) 条边的无向图和一个源点 \(s\)。要求删除一个不同与 \(s\) 的结点 \(u\)，使得有最多的点到 \(s\) 的最短距离改变。求出此时最短距离改变的结点的数量。

\(n\le2\times10^5,m\le3\times10^5\)。

\(\mathcal{Solution}\)

首先，以 \(s\) 为源点跑一个单源最短路。设 \(s\) 到 \(u\) 的距离为 \(dist_u\)。

接着枚举所有点 \(u\) 与其一条边 \((u,v)\)。若满足 \(dist_u+\operatorname{cost}(u,v)=dist_v\)，则表示该边是 \(v\) 最短路径的一条转移边，将其加入新图 \(G\) 中。

显然 \(G\) 是有向无环图，所以直接建立支配树，求出子树大小最大的结点即可。

\(\mathcal{Code}\)

#include <queue>

#include <cstdio>

#include <vector>

#include <cstring>

#define cost first

#define node second

#define adj( g, u, v ) \

	for ( int _eid = g.head[u], v; v = g.to[_eid], _eid; _eid = g.nxt[_eid] )

typedef long long LL;

typedef std::pair<LL, int> pli;

const int MAXN = 2e5, MAXM = 6e5, MAXLG = 17;

int n, m, s, dep[MAXN + 5], siz[MAXN + 5], rnk[MAXN + 5], fa[MAXN + 5][MAXLG + 5];

LL dist[MAXN + 5];

std::queue<int> que;

std::vector<int> pre[MAXN + 5];

std::vector<pli> sour[MAXN + 5];

inline int rint () {

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

	for ( ; s < '0' || '9' < s; s = getchar () );

	for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );

	return x;

}

struct Graph {

	int ecnt, head[MAXN + 5], to[MAXM + 5], nxt[MAXM + 5], ind[MAXN + 5];

	inline void link ( const int s, const int t ) {

		++ ind[to[++ ecnt] = t], nxt[ecnt] = head[s], head[s] = ecnt;

		pre[t].push_back ( s );

	}

} dag, domt;

inline int LCA ( int u, int v ) {

	if ( dep[u] < dep[v] ) u ^= v ^= u ^= v;

	for ( int i = 17; ~ i; -- i ) if ( dep[fa[u][i]] >= dep[v] ) u = fa[u][i];

	if ( u == v ) return u;

	for ( int i = 17; ~ i; -- i ) if ( fa[u][i] ^ fa[v][i] ) u = fa[u][i], v = fa[v][i];

	return fa[u][0];

}

inline void calc ( const int u ) {

	siz[u] = 1;

	adj ( domt, u, v ) calc ( v ), siz[u] += siz[v];

}

inline void Dijkstra ( const int s ) {

	static bool vis[MAXN + 5] {};

	static std::priority_queue<pli, std::vector<pli>, std::greater<pli> > pque;

	memset ( dist, 0x3f, sizeof dist ), pque.push ( { dist[s] = 0, s } );

	while ( ! pque.empty () ) {

		pli p = pque.top (); pque.pop ();

		if ( vis[p.node] ) continue;

		vis[p.node] = true;

		for ( pli e: sour[p.node] ) {

			if ( ! vis[e.node] && p.cost + e.cost < dist[e.node] ) {

				pque.push ( { dist[e.node] = p.cost + e.cost, e.node } );

			}

		}

	}

}

int main () {

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

	for ( int i = 1, u, v, w; i <= m; ++ i ) {

		u = rint (), v = rint (), w = rint ();

		sour[u].push_back ( { LL ( w ), v } );

		sour[v].push_back ( { LL ( w ), u } );

	}

	Dijkstra ( s );

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

		for ( pli e: sour[i] ) {

			if ( dist[e.node] == dist[i] + e.cost ) {

				dag.link ( i, e.node );

			}

		}

	}

	que.push ( s );

	int cnt = 0;

	for ( int u; ! que.empty (); que.pop () ) {

		rnk[++ cnt] = u = que.front ();

		adj ( dag, u, v ) if ( ! -- dag.ind[v] ) que.push ( v );

	}

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

		int u = rnk[i], f = 0;

		if ( ! pre[u].empty () ) f = pre[u][0];

		for ( int j = 1; j < ( int ) pre[u].size (); ++ j ) f = LCA ( f, pre[u][j] );

		dep[u] = dep[fa[u][0] = f] + 1, domt.link ( f, u );

		for ( int j = 1; j <= 17; ++ j ) fa[u][j] = fa[fa[u][j - 1]][j - 1];

	}

	calc ( s );

	int ans = 0;

	for ( int i = 1; i <= n; ++ i ) if ( i ^ s ) ans = ans < siz[i] ? siz[i] : ans;

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

	return 0;

}

巴特西

Solution -「CF 757F」Team Rocket Rises Again

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章