列表

详情

NC51309. Traffic Real Time Query System

描述

City C is really a nightmare of all drivers for its traffic jams. To solve the traffic problem, the mayor plans to build a RTQS (Real Time Query System) to monitor all traffic situations. City C is made up of N crossings and M roads, and each road connects two crossings. All roads are bidirectional. One of the important tasks of RTQS is to answer some queries about route-choice problem. Specifically, the task is to find the crossings which a driver MUST pass when he is driving from one given road to another given road.

输入描述

There are multiple test cases.
For each test case:
The first line contains two integers N and M, representing the number of the crossings and roads.
The next M lines describe the roads. In those M lines, the ith line (i starts from 1)contains two integers X_i and Y_i, representing that roadi connects crossing X_i and .
The following line contains a single integer Q, representing the number of RTQs.
Then Q lines follows, each describing a RTQ by two integers S and  meaning that a driver is now driving on the roads and he wants to reach roadt . It will be always at least one way from roads to roadt.
The input ends with a line of “0 0”.
Please note that: , ,, ,

输出描述

For each RTQ prints a line containing a single integer representing the number of crossings which the driver MUST pass.

示例1

输入: 

5 6
1 2
1 3
2 3
3 4
4 5
3 5
2
2 3
2 4
0 0

输出: 

0
1

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 45ms, 内存消耗: 11032K, 提交时间: 2022-08-21 14:30:57 

#include<bits/stdc++.h>
#define M 10009
#define N 100009
#define inf 99999999
using namespace std;
struct node
{
    int u,v,next,vis;
}edge[N*2];
stack<int>q;
int t,head[M],dfn[M],low[M],cut[M],use[N*2],ind,num,belong[N*2];
struct Tree
{
    int v;
    Tree(){}
    Tree(int vv):v(vv){}
};
vector<Tree>Edge[M+N];
void init()
{
    t=0;
    memset(head,-1,sizeof(head));
    memset(edge,0,sizeof(edge));
}
void add(int u,int v)
{
    edge[t].u=u;
    edge[t].v=v;
    edge[t].next=head[u];
    head[u]=t++;
}
void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++ind;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(edge[i].vis)continue;
        edge[i].vis=edge[i^1].vis=1;
        q.push(i);
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])
            {
                num++;
                cut[u]++;
                int j;
                do
                {
                    j=q.top();
                    q.pop();
                    belong[j]=belong[j^1]=num;
                }while(j!=i);
            }
        }
        else
            low[u]=min(low[u],dfn[v]);
    }
    if(fa<0)
        cut[u]--;
}
void solve(int n)
{
    ind=num=0;
    memset(dfn,0,sizeof(dfn));
    memset(cut,0,sizeof(cut));
    for(int i=1;i<=n;i++)
        if(!dfn[i])
        tarjan(i,-1);
}
struct LCA
{
    int u,v,w,next;
}lca[N*3];
int t1,head1[N*2],f[N*2],dis[N*2];
void Init()
{
    t1=0;
    memset(head1,-1,sizeof(head1));
}
void Addlca(int u,int v)
{
    lca[t1].u=u;
    lca[t1].v=v;
    lca[t1].next=head1[u];
    head1[u]=t1++;
}
int finde(int x)
{
    if(x!=f[x])
        f[x]=finde(f[x]);
    return f[x];
}
void make(int a,int b)
{
    f[finde(a)]=finde(b);
}
void dfs(int u)
{
    use[u]=1;
    for(int i=0;i<(int)Edge[u].size();i++)
    {
        int v=Edge[u][i].v;
        if(!use[v])
        {
            dis[v]=dis[u]+1;
            dfs(v);
            f[v]=u;
            make(u,v);
        }
    }
    for(int i=head1[u];i!=-1;i=lca[i].next)
    {
        int v=lca[i].v;
        if(use[v])
            lca[i].w=lca[i^1].w=f[finde(v)];
    }
}
void slove()
{
    dis[1]=0;
    for(int i=0;i<=num;i++)
    f[i]=i;
    memset(use,0,sizeof(use));
    for(int i=1;i<=num;i++)
        if(!use[i])
        dfs(i);
    for(int i=0;i<t1;i+=2)
    {
        int u=lca[i].u;
        int v=lca[i].v;
        int mid=lca[i].w;
        printf("%d\n",(dis[u]+dis[v]-2*dis[mid])/2);
    }
}
int main()
{
    int n,m,i,u,v;
    while(scanf("%d%d",&n,&m),m||n)
    {
        init();
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        solve(n);
        memset(use,0,sizeof(use));
        for(u=1;u<=n;u++)
        {
            if(cut[u])
            {
                ++num;
                for(i=head[u];i!=-1;i=edge[i].next)
                {
                    if(!use[belong[i]])
                    {
                        Edge[num].push_back(belong[i]);
                        Edge[belong[i]].push_back(num);
                        use[belong[i]]=1;
                    }
                }
                for(i=head[u];i!=-1;i=edge[i].next)
                    use[belong[i]]=0;
            }
        }
        int Q;
        scanf("%d",&Q);
        Init();
        while(Q--)
        {
            scanf("%d%d",&u,&v);
            Addlca(belong[u*2-1],belong[v*2-1]);
            Addlca(belong[v*2-1],belong[u*2-1]);
        }
        slove();
        for(i=0;i<=num;i++)
            Edge[i].clear();
    }
    return 0;
}

C++ 解法, 执行用时: 38ms, 内存消耗: 12720K, 提交时间: 2021-09-02 22:18:16 

#include<bits/stdc++.h>

using namespace std;

const int N=4e4+90,M=4e5+90;

int cnt,nxt[M],head[N],ver[M];
int n,m;
int dfn[N],low[N],timestamp;
int stac[N],top;
int v_dcc;
vector<int> V[N],edge[N];
int ances[N][40],dep[N];
int t,we[N];

void add(int a,int b){
	nxt[++cnt]=head[a],head[a]=cnt,ver[cnt]=b;
}

void add_ict(int a,int b){
	edge[a].push_back(b);
	edge[b].push_back(a);
}

void Tarjan(int i,int fa){
	dfn[i]=low[i]=++timestamp;
	stac[++top]=i;
	for(int io=head[i];io;io=nxt[io])
	{
		int v=ver[io];
		if(!dfn[v])
		{
			Tarjan(v,i);
			low[i]=min(low[v],low[i]);
			if(low[v]>=dfn[i])
			{
				add_ict(++v_dcc,i);
				int p;
				do
				{
					p=stac[top--];
					add_ict(p,v_dcc);
				}while(p!=v);
			}
		}
		else if(v!=fa)
			low[i]=min(low[i],dfn[v]);
	}
}

int LCA(int x,int y){
	if(dep[x]>dep[y]) swap(x,y);
	for(int i=t;i>=0;i--)
		if(dep[ances[y][i]]>=dep[x]) y=ances[y][i];
	if(x==y) return x;
	for(int i=t;i>=0;i--)
		if(ances[x][i]!=ances[y][i])
			x=ances[x][i],y=ances[y][i];
	return ances[x][0];
}

int workf(int x,int y){
	int lca=LCA(x,y);
	return (dep[x]+dep[y]-2*dep[lca])/2-1;
}

void dfs(int i,int fa){
	we[i]=1;ances[i][0]=fa;
	dep[i]=dep[fa]+1;
	for(int j=1;j<=t;j++)
		ances[i][j]=ances[ances[i][j-1]][j-1];
	for(int j=0;j<edge[i].size();j++)
	{
		int v=edge[i][j];
		if(v==fa) continue;
		if(!we[v]) dfs(v,i);
	}
}

void work(){
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b),add(b,a);
	}
	v_dcc=n;
	for(int i=1;i<=n;i++)
		if(!dfn[i]) Tarjan(i,0);
	t=log2(v_dcc);
	for(int i=1;i<=v_dcc;i++)
		if(!we[i]) dfs(i,0);
	int q;
	scanf("%d",&q);
	while(q--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int as=max(workf(ver[x<<1],ver[y<<1]),workf(ver[(x<<1)-1],ver[y<<1]));
		as=max(as,workf(ver[(x<<1)-1],ver[(y<<1)-1]));
		as=max(as,workf(ver[x<<1],ver[(y<<1)-1]));
		printf("%d\n",as);
	}
}

void init(){
	for(int i=1;i<=v_dcc;i++) V[i].clear(),edge[i].clear();
	cnt=0,v_dcc=0;
    memset(nxt,0,sizeof nxt);
	memset(head,0,sizeof head);
	memset(low,0,sizeof low);
	memset(dfn,0,sizeof dfn);
	timestamp=0,top=0,t=0;
	memset(ances,0,sizeof ances);
	memset(dep,0,sizeof dep);
	memset(we,0,sizeof we);
}

int main(){
	while(scanf("%d%d",&n,&m),n||m)
		work(),init();
	
	return 0;
}

上一题

© 2024 nowcoder.com