自动搬运

查看原文

来自洛谷，原作者为

	糪眾脦颰罷 这个家伙很帅，什么也没有留下

搬运于2025-08-24 22:02:44，当前版本为作者最后更新于2019-07-20 09:03:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

BFS（无需缩点！）

根据题意:

两条道路是没有相交的

不难得出：

若一个西海岸的点$x$能连到纵坐标为$y1$和纵坐标为$y2$的东海岸(满足$y1<y2$)，那么对于在东海岸的纵坐标为$[y1,y2]$的点若有连向西海岸的路，其都可以到达点$x$。

不懂得看一下图自己再yy一下:

算法流程

难以口胡，实在看不懂就看代码吧 1.广搜一遍求出东海岸到不了的点

2.建反图，将可到达的东海岸的点进行标号

3.进行按y坐标从小到大由东海岸向西海岸的广搜，将遇到的点都标记为当前点的标号

4.进行按y坐标从大到小由东海岸向西海岸的广搜，将遇到的点都标记为当前点的标号

代码:

#include<bits/stdc++.h>
#define MAXN 300010
using namespace std;
int n,m,A,B,Head[MAXN],TotEdge,TotWest,TotEast,cnt,L[MAXN],R[MAXN],HeadF[MAXN],TotEdgeF;
struct Edge{
	int ed,last;
}G[MAXN*6],F[MAXN*6];
struct Point{
	int i,y,num;
}West[MAXN],East[MAXN];
queue<int> Q;
bool mark[MAXN];
bool cmp(Point XX,Point YY){
	return XX.y>YY.y;
}
void Rd(int &res){
	res=0;char ch=getchar();
	while('0'>ch||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=(res<<3)+(res<<1)+(ch-'0'),ch=getchar();
}
void Add(int st,int ed){
	TotEdge++,TotEdgeF++;
	G[TotEdge]=(Edge){ed,Head[st]};
	F[TotEdgeF]=(Edge){st,HeadF[ed]};
	Head[st]=TotEdge;
	HeadF[ed]=TotEdgeF;
}
int main(){
	memset(Head,-1,sizeof(Head));
	memset(HeadF,-1,sizeof(HeadF));
	Rd(n),Rd(m),Rd(A),Rd(B);
	for(int i=1;i<=n;i++){
		int x,y;
		Rd(x),Rd(y);
		if(x==0)West[++TotWest]=(Point){i,y};
		else if(x==A)East[++TotEast]=(Point){i,y};
	}
	for(int i=1;i<=m;i++){
		int x,y,k;
		Rd(x),Rd(y),Rd(k);
		if(k==1)Add(x,y);
		else Add(x,y),Add(y,x);
	}
	sort(West+1,West+1+TotWest,cmp);
	sort(East+1,East+1+TotEast,cmp);
	for(int i=1;i<=TotWest;i++){
		if(mark[West[i].i])continue;
		mark[West[i].i]=true;
		Q.push(West[i].i);
		while(!Q.empty()){
			int now=Q.front();
			Q.pop();
			for(int i=Head[now];~i;i=G[i].last){
				int t=G[i].ed;
				if(mark[t])continue;
				mark[t]=true;
				Q.push(t);
			}
		}
	}
	for(int i=1;i<=TotEast;i++){
		if(!mark[East[i].i])continue;
		East[i].num=++cnt;
	}
	while(!Q.empty())Q.pop();
	for(int i=1;i<=TotEast;i++){
		if(!mark[East[i].i])continue;
		if(L[East[i].i])continue;
		Q.push(East[i].i);
		L[East[i].i]=East[i].num;
		while(!Q.empty()){
			int now=Q.front();
			Q.pop();
			for(int j=HeadF[now];~j;j=F[j].last){
				int t=F[j].ed;
				if(L[t])continue;
				L[t]=East[i].num;
				Q.push(t);
			}
		}
	}
	while(!Q.empty())Q.pop();
	for(int i=1;i<=TotEast;i++){
		if(!mark[East[i].i])continue;
	}
	for(int i=TotEast;i>=1;i--){
		if(!mark[East[i].i])continue;
		if(R[East[i].i])continue;
		Q.push(East[i].i);
		R[East[i].i]=East[i].num;
		while(!Q.empty()){
			int now=Q.front();
			Q.pop();
			for(int j=HeadF[now];~j;j=F[j].last){
				int t=F[j].ed;
				if(R[t])continue;
				R[t]=East[i].num;
				Q.push(t);
			}
		}
	}
	for(int i=1;i<=TotWest;i++){
		if(L[West[i].i]==0)puts("0");
		else printf("%d\n",R[West[i].i]-L[West[i].i]+1);
	}
	return 0;
}