【51nod1815】调查任务（Tarjan+拓扑）

点此看题面

大致题意： 有\(N\)个城市由\(M\)条单向道路（图不一定联通），每个城市有一个发达程度\(a[i]\)，要求你求出首都\(S\)到城市\(i\)的一条路径上的两个不同城市\(x,y\)的\(a[x]\%a[y]\)的最大值（包括\(S\)和\(i\)），若无法到达输出\(-1\)。

一个简单的问题

首先，我们来考虑一个问题：若你已知若干个数，如何求出其中两个数相模后的最大值？

答案是显然的，用次大值（严格次大）去模最大值。

下面给出证明：

设这些数中的最大值为\(Max1\)，严格次大值为\(Max2\)，则

若一个数取\(Max1\)，另一个数取\(a（a<Max1）\)，显然，此时模后得到的值为\(a\)。说明当\(a\)小于\(Max1\)时，\(a\)越大越好，则我们可证，当一个数取\(Max1\)时，只有另一个数取\(Max2\)时，才能使相模后得到的结果最大，且得到的结果是\(Max2\)。

如果不取\(Max1\)，假设我们取得两个数是\(x,y（x≤y）\)，则它们相模后的结果一定小于\(y\)。又因为不能取\(Max1\)，所以\(y\)最大能取\(Max2\)，所以最终的结果一定小于\(Max2\)，显然没有一个数取\(Max1\)，一个数取\(Max2\)时得到的结果更优。

综上所述，当一个数取最大值，一个数取严格次大值时，两数相模的结果最大。

具体做法

那么这道题的做法就比较清晰了：

首先用\(Tarjan\)对原图进行缩点，将原图变成一棵树。

然后对缩点后的图按照拓扑序扫一遍对每一个城市预处理出答案。

最后就是对每一个询问输出答案了。

比较重要的一点就是要注意\(x\)和\(y\)两个城市必须在同一条路径上，我就为此而\(WA\)了无数次。。。

代码

#include<bits/stdc++.h>

#define N 400000

#define M 2000000

using namespace std;

int n,m,Q,s,tot,sum,cnt,top,a[N+5],lnk[N+5],nlnk[N+5],max1[N+5],max2[N+5],max3[N+5],max4[N+5],low[N+5],dfn[N+5],pos[N+5],que[N+5],Stack[N+5],IN[N+5];

bool vis[N+5];

struct edge

{

	int to,nxt;

}e[M+5],ne[M+5];//e[]存储缩点前的边，ne[]存储缩点后的边

void read(int &x)

{

	x=0;char ch=getchar();

	while(ch<'0'||ch>'9') ch=getchar();

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

}

void write(int x)

{

	if(x>9) write(x/10);

	putchar(x%10+'0');

}

void add(int x,int y)

{

	e[++cnt].to=y,e[cnt].nxt=lnk[x],lnk[x]=cnt;

}

void nadd(int x,int y)

{

	ne[++cnt].to=y,ne[cnt].nxt=nlnk[x],nlnk[x]=cnt;

}

void Tarjan(int x)//用Tarjan将原图缩点，模板不解释

{

	dfn[x]=low[x]=++tot,Stack[++top]=x,vis[x]=1;

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

	if(!dfn[e[i].to]) Tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]);

	else if(vis[e[i].to]) low[x]=min(low[x],dfn[e[i].to]);

	if(low[x]==dfn[x])

	{

		pos[x]=++sum,vis[x]=0,max1[sum]=a[x];

		while(Stack[top]!=x)

		{

			pos[Stack[top]]=sum,vis[Stack[top]]=0;

			if(a[Stack[top]]>max1[sum]) max2[sum]=max1[sum],max1[sum]=a[Stack[top]];//更新这个强连通分量中的最大值和次大值

			else if(a[Stack[top]]!=max1[sum]&&a[Stack[top]]>max2[sum]) max2[sum]=a[Stack[top]];

			top--;

		}

		top--;

	}

}

void topo_sort(int s)//按拓扑序预处理出答案

{

	int H=0,T=1;

	que[1]=s,vis[s]=1;

	while(H<T)

	{

		int x=que[++H];

		for(int i=nlnk[x];i;i=ne[i].nxt)

		{

			++IN[ne[i].to];

			if(vis[ne[i].to]) continue;

			vis[ne[i].to]=1,que[++T]=ne[i].to;

		}

	}

	H=0,T=1,que[1]=s;

	while(H<T)

	{

		int x=que[++H];

		for(int i=nlnk[x];i;i=ne[i].nxt)

		{

			//预处理出答案

			max2[ne[i].to]=max(max2[ne[i].to],max2[x]);

            if(max1[ne[i].to]!=max3[x]) max2[ne[i].to]=max(max2[ne[i].to],min(max1[ne[i].to],max3[x]));

            else max2[ne[i].to]=max(max2[ne[i].to],max4[x]);

            if(max3[x]>max3[ne[i].to]) max4[ne[i].to]=max3[ne[i].to],max3[ne[i].to]=max3[x];

            else if(max3[ne[i].to]>max3[x]&&max3[x]>max4[ne[i].to]) max4[ne[i].to]=max3[x];

            if(max4[x]>max3[ne[i].to]) max4[ne[i].to]=max3[ne[i].to],max3[ne[i].to]=max4[ne[i].to];

            else if(max3[ne[i].to]>max4[x]&&max4[x]>max4[ne[i].to]) max4[ne[i].to]=max4[x];

			if(!(--IN[ne[i].to])) que[++T]=ne[i].to;

		}

	}

}

int main()

{

	read(n),read(m),read(Q),read(s);

	for(int i=1;i<=n;i++) read(a[i]);

	for(int i=1,x,y;i<=m;i++)

		read(x),read(y),add(x,y);

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

		if(!dfn[i]) Tarjan(i);//Tarjan缩点

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

		for(int j=lnk[i];j;j=e[j].nxt)

			if(pos[i]!=pos[e[j].to]) nadd(pos[i],pos[e[j].to]);//处理出缩点之后的图

	memcpy(max3,max1,sizeof(max3)),memcpy(max4,max2,sizeof(max4)),topo_sort(pos[s]);//预处理答案

	while(Q--)

	{

		int x;read(x);

		if(!vis[pos[x]]) printf("-1 ");//判断与s是否联通，不连通输出-1

		else write(max2[pos[x]]),putchar(' ');//若联通输出答案

	}

	return 0;

}

巴特西

【51nod1815】调查任务（Tarjan+拓扑）

一个简单的问题

具体做法

代码

最新文章

热门文章