【codeforces gym】Increasing Costs

Description

　　给你一个\(n\)个点无重边无自环的无向连通图，每条边有一个边权，对于每一条边，询问去掉这条边之后有多少个点到\(1\)号点的最短路会发生改变

Solution

　　会用到一个叫做灭绝树的东西（这个名字好霸气qwq）

　　其实不算是什么特别高大上的玩意：灭绝树其实就是一个点灭绝后它的子树内的所有点都灭绝

　　然后所谓的“灭绝”其实可以理解为。。满足什么条件之类的，在不同的题目中有所不同（比如说在这题里面就是。。走不到）

　　然后这道题的话，因为是删边，我们可以将边也看成一个点

　　首先求出到\(1\)的最短路，然后对于原图中的一条边权为\(w\)的边\((i,j)\)，如果说\(dis[j]=dis[i]+w\)的话，就在新图中连\((i,num)\)和\((num,j)\)的有向边，其中\(num\)表示的是这条边对应的节点

　　注意到如果说我们将一条边删掉，也就是相当于将这条边对应的节点\(num\)删掉，由于这条边删掉了，由这条边得到的最短路也就不能走了，对应到新图中就是\(num\)这个节点不能走到，接着那些的只能由它走到的后继也就不能走到了，以此类推

　　所以我们考虑用这样的方式建一棵树：我们将新图所有的边反过来建，然后对整个反过来的新图拓扑排序，从后往前处理每一个节点在树上面的\(fa\)，那么处理到一个节点的时候，新图中所有能走到当前节点的点的\(fa\)都已经处理好了，然后我们将当前节点的\(fa\)设为所有能走到这个节点的那些点的\(lca\)

　　这样建完之后会发现，删掉一条边对应的点\(num\)之后不能走到的点其实就是其整个子树中的点

　　所以我们只要建出树之后计算一下每个节点的子树大小就好了

　　代码大概长这个样子

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define ll long long

using namespace std;

const int N=4e5+10,TOP=20;

const ll inf=1LL<<60;

struct xxx{

	int y,nxt,id,dis;

}a[N*2];

struct Data{

	int node;

	ll dis;

	Data(){}

	Data(int node1,ll dis1){node=node1; dis=dis1;}

	friend bool operator < (Data x,Data y){return x.dis>y.dis;}

};

priority_queue<Data> q;

queue<int> q1;

vector<int> pre[N];

int lis[N];

int h[N],f[N][TOP+1],dep[N];

ll dis[N];

int vis[N],d[N],sz[N];

int n,m,tot,S;

void add(int x,int y,int dis,int id){a[++tot].y=y; a[tot].nxt=h[x]; h[x]=tot; a[tot].id=id; a[tot].dis=dis;}

void print(vector<int> x){

	for (int i=0;i<x.size();++i) printf("%d ",x[i]); printf("\n");

}

void dij(){

	int u,v;

	while (!q.empty()) q.pop();

	for (int i=1;i<=n;++i) dis[i]=inf,vis[i]=false;

	dis[S]=0;

	q.push(Data(S,dis[S]));

	while (!q.empty()){

		v=q.top().node; q.pop();

		if (vis[v]) continue;

		vis[v]=1;

		for (int i=h[v];i!=-1;i=a[i].nxt){

			u=a[i].y;

			if (vis[u]) continue;

			if (dis[u]>dis[v]+a[i].dis){

				dis[u]=dis[v]+a[i].dis;

				q.push(Data(u,dis[u]));

			}

		}

	}

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

		for (int i=h[x];i!=-1;i=a[i].nxt){

			u=a[i].y;

			if (dis[u]==dis[x]+a[i].dis){

				pre[u].push_back(a[i].id+n);

				pre[a[i].id+n].push_back(x);

				++d[a[i].id+n];

				++d[x];

			}

		}

	}

}

int get_lca(int x,int y){

	if (!x||!y) return x+y;

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

	for (int i=TOP;i>=0;--i)

		if (dep[f[x][i]]>=dep[y]) x=f[x][i];

	if (x==y) return x;

	for (int i=TOP;i>=0;--i)

		if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];

	return f[x][0];

}

void topo(int n){

	int u,v;

	while (!q1.empty()) q1.pop();

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

		if (d[i]==0) q1.push(i);

	lis[0]=0;

	while (!q1.empty()){

		v=q1.front(); q1.pop();

		lis[++lis[0]]=v;

		for (int i=0;i<pre[v].size();++i){

			u=pre[v][i];

			--d[u];

			if (!d[u]) q1.push(u);

		}

	}

}

void get_fa(int x){

	int lca,Sz=pre[x].size();

	if (Sz==0){

		f[x][0]=0;

	}

	else if (Sz==1)

		f[x][0]=pre[x][0];

	else if (Sz>=2){

		lca=get_lca(pre[x][0],pre[x][1]);

		for (int i=2;i<Sz;++i)

			lca=get_lca(lca,pre[x][i]);

		f[x][0]=lca;

	}

	for (int i=1;i<=TOP;++i) f[x][i]=f[f[x][i-1]][i-1];

	dep[x]=dep[f[x][0]]+1;

	sz[x]=(x<=n);

}

void solve(){

	topo(n+m);

	for (int i=lis[0];i>=1;--i)

		get_fa(lis[i]);

	for (int i=1;i<=lis[0];++i)

		sz[f[lis[i]][0]]+=sz[lis[i]];

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

#endif

	int x,y,z;

	scanf("%d%d",&n,&m);

	memset(h,-1,sizeof(h));

	tot=0;

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

		scanf("%d%d%d",&x,&y,&z);

		add(x,y,z,i);

		add(y,x,z,i);

	}

	S=1;

	dij();

	solve();

	//for (int i=1;i<=n+m;++i) printf("%d " ,f[i][0]); printf("\n");

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

		printf("%d\n",sz[i+n]);

}

巴特西

【codeforces gym】Increasing Costs

Description

Solution

最新文章

热门文章