题解 P4700 【[CEOI2011]Traffic】

· · 题解

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;
}