Description

给定一个n个点，m条边的带权无向图，和起点S。请你选择一个点u(u!=S)，使得在图中删掉点u 后，有尽可能多的点到S的最短距离改变。

Solution

先建出最短路DAG，在DAG中跑出灭绝树

灭绝树是一个点灭绝后子树中的点都灭绝的一棵树(灭绝在不同题目中意义不同)

先拓扑一下，每个点的最短路依赖的点就在它拓扑序前了

我们在拓扑序中从前往后扫

扫到点x，它的依赖点都已求出灭绝树父亲

x的灭绝树父亲就是它所有依赖点的灭绝树LCA

LCA可以用树上倍增求一下

Notice

1.可能有些点不连通

2.long long

Code

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cctype>

#include <algorithm>

using namespace std;

typedef long long LL;

const int M=200007;

const int E=600007;

inline int rd(){

	int x=0;bool f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(;isdigit(c);c=getchar()) x=x*10+c-48;

	return f?x:-x;

}

int n,m,S;

struct node{int x,y;LL d;}ed[E];

int g[M],te;

struct edge{

	int y,next;

	LL d;

}e[E];

void addedge(int x,int y,LL z){

	e[++te].y=y;

	e[te].d=z;

	e[te].next=g[x];

	g[x]=te;

}

int gd[M],td, gu[M],tu;

struct link{

	int y,next;

}dw[E],up[E];

void adddw(int x,int y){

	dw[++td].y=y;

	dw[td].next=gd[x];

	gd[x]=td;

}

void addup(int x,int y){

	up[++tu].y=y;

	up[tu].next=gu[x];

	gu[x]=tu;

}

int que[M],vis[M];

LL dis[M];

void inc(int &x){x++;if(x>=M)x=0;}

void spfa(int ss){

	int h=0,t=1,x,p,y;

	que[t]=ss;

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

	dis[ss]=0;

	vis[ss]=1;

	while(h^t){

		inc(h); x=que[h];

		for(p=g[x];p;p=e[p].next){

			y=e[p].y;

			if(dis[x]+e[p].d<dis[y]){

				dis[y]=dis[x]+e[p].d;

				if(!vis[y]){

					vis[y]=1;

					inc(t); que[t]=y;

				}

			}

		}

		vis[x]=0;//***********

	}

}

int indu[M];

void Dag(){

	int i,x,y;

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

		x=ed[i].x;

		y=ed[i].y;

		if(dis[x]>dis[y]) swap(x,y);

		if(dis[x]+ed[i].d==dis[y]){

			adddw(x,y);

			addup(y,x);

			indu[y]++;

		}

	}

}

void topu(){

	int h=0,t=1,x,p,y;

	que[1]=S;

	while(h^t){

		x=que[++h];

		for(p=gd[x];p;p=dw[p].next){

			y=dw[p].y;

			indu[y]--;

			if(indu[y]==0) que[++t]=y;

		}

	}

	n=t;//排掉不连通的点*************************

}

int pre[M][22];

int dep[M];

int sz[M];

int unit;

int LCA(int x,int y){

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

	int t;

	for(t=unit;t>=0;t--){

		if(dep[pre[x][t]]>=dep[y]) x=pre[x][t];

	}

	if(x==y) return x;

	for(t=unit;t>=0;t--){

		if(pre[x][t]!=pre[y][t]) x=pre[x][t], y=pre[y][t];

	}

	return pre[x][0];

}

int main(){

	int i,j,p,x,y,z;

	n=rd(), m=rd(), S=rd();

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

		x=rd(),y=rd(),z=rd();

		addedge(x,y,z);

		addedge(y,x,z);

		ed[i].x=x;

		ed[i].y=y;

		ed[i].d=(LL)z;

	}

	spfa(S);

	Dag();

	topu();

	unit=(int)(log(n)/log(2))+1;

	for(i=0;i<=unit;i++) pre[S][i]=S;

	dep[S]=1;

	for(i=2;i<=n;i++){

		x=que[i];

		z=0;

		for(p=gu[x];p;p=up[p].next){

			y=up[p].y;

			if(!z) z=y;

			else z=LCA(z,y);

		}

		pre[x][0]=z;

		dep[x]=dep[z]+1;

		for(j=1;j<=unit;j++) pre[x][j]=pre[pre[x][j-1]][j-1];

	}

	for(i=n;i>1;i--){

		x=que[i];

		sz[x]++;

		sz[pre[x][0]]+=sz[x];

	}

	sz[S]++;//不是sz[1]++; 

	int ans=0;

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

		ans=max(ans,sz[que[i]]);

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

	return 0;

}

巴特西

codeforces 757F - 最短路DAG+灭绝树

Description

Solution

Notice

Code

最新文章

热门文章