CF757F Team Rocket Rises Again

题意

建出最短路图（DAG）之后就跟这题一样了。
code:
#include<bits/stdc++.h>

using namespace std;

#define int long long

#define pii pair<int,int>

#define mkp make_pair

#define fir first

#define sec second

const int maxn=2*1e5+10;

const int maxm=3*1e5+10;

int n,m,st,ans,cnt;

int ex[maxm],ey[maxm],ew[maxm],head[maxn],dis[maxn],size[maxn],dep[maxn],deg[maxn];

int f[maxn][20];

bool vis[maxn];

struct edge{int to,nxt;}e[maxn];

struct Edge{int to,dis;};

vector<Edge>E[maxn],e1[maxn],e2[maxn];

inline int read()

{

	char c=getchar();int res=0,f=1;

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();

	return res*f;

}

inline void add(int u,int v)

{

	e[++cnt].nxt=head[u];

	head[u]=cnt;

	e[cnt].to=v;

}

inline int lca(int x,int y)

{

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

	for(int i=18;~i;i--)if(dep[f[y][i]]>=dep[x])y=f[y][i];

	if(x==y)return x;

	for(int i=18;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];

	return f[x][0];

}

inline void dijstra()

{

	memset(dis,0x3f,sizeof(dis));

	priority_queue<pii>q;

	dis[st]=0;q.push(mkp(0,st));

	while(!q.empty())

	{

		int x=q.top().sec;q.pop();

		if(vis[x])continue;

		vis[x]=1;

		for(unsigned int i=0;i<E[x].size();i++)

		{

			int y=E[x][i].to;

			if(dis[y]>dis[x]+E[x][i].dis)

			{

				dis[y]=dis[x]+E[x][i].dis;

				q.push(mkp(-dis[y],y));

			}

		}

	}

}

inline void topsort()

{

	queue<int>q;

	q.push(st);dep[st]=1;

	while(!q.empty())

	{

		int x=q.front();q.pop();

		for(unsigned int i=0;i<e1[x].size();i++)

		{

			int y=e1[x][i].to;

			deg[y]--;

			if(!deg[y])

			{

				int z=0;

				for(unsigned int j=0;j<e2[y].size();j++)z=!z?e2[y][j].to:lca(z,e2[y][j].to);

				add(z,y);f[y][0]=z;dep[y]=dep[z]+1;

				for(int j=1;j<=18;j++)f[y][j]=f[f[y][j-1]][j-1];

				q.push(y);

			}

		}

	}

}

void dfs(int x)

{

	size[x]=1;

	for(int i=head[x];i;i=e[i].nxt)

	{

		int y=e[i].to;

		dfs(y);size[x]+=size[y];

	}

}

signed main()

{

	n=read(),m=read(),st=read();

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

	{

		ex[i]=read(),ey[i]=read(),ew[i]=read();

		E[ex[i]].push_back((Edge){ey[i],ew[i]});

		E[ey[i]].push_back((Edge){ex[i],ew[i]});

	}

	dijstra();

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

	{

		if(dis[ex[i]]==dis[ey[i]]+ew[i])swap(ex[i],ey[i]);

		if(dis[ey[i]]==dis[ex[i]]+ew[i])e1[ex[i]].push_back((Edge){ey[i],1}),e2[ey[i]].push_back((Edge){ex[i],1}),deg[ey[i]]++;

	}

	topsort();dfs(st);

	for(int i=1;i<=n;i++)if(i!=st)ans=max(ans,size[i]);

	printf("%lld",ans);

	return 0;

}
巴特西

CF757F Team Rocket Rises Again

题意

最新文章

热门文章
