题目地址：洛谷：【P4700】[CEOI2011]Traffic – 洛谷、BZOJ：Problem 2387. — [Ceoi2011]Traffic

题目描述

格丁尼亚的中心位于Kacza河中的一座岛屿。每天清晨，成千上万辆汽车通过岛屿从西岸的住宅区（由桥连接岛的西部）到东岸的工业区（由桥连接岛的东部）。该岛类似于矩形，它的边平行于主方向。故可将它看作是笛卡尔坐标系中的一个A*B的矩形，它的对角分别为（0, 0）和（A, B）。岛上有n个交通节点，编号为1…n（junction,此处可理解为广义的路口），第i个节点坐标为(xi, yi)。如果一个节点的坐标为(0, y)，它就位于岛的西岸。类似的，坐标为(A, y)的节点位于岛的东岸。各个节点由街道连接，每条街道用线段连接两个节点。街道有单向行驶或双向行驶之分。除端点外任意两条街道都没有公共点。也没有桥梁或者隧道。你不能对道路网络形状做任何其他假设。沿河岸的街道或节点可能没有入口或者出口街道。由于交通堵塞日趋严重，市长聘请你测试岛上当前的道路网是否足够。要求你写一个程序确定从岛的西岸的每个节点能够到达东岸的多少个节点。

题意简述

在平面直角坐标系上有 n 个点，其中第 i 个点的坐标是 (xi,yi) ，所有点在一个以 (0,0) 和 (A,B) 为相对顶点的矩形内。
如果 xi=0 ，那么我们称这个点在西侧。如果 xi=A ，那么我们称这个点在东侧。
这些点之间有 m 条边，每条边可能是有向边也可能是无向边，保证边在交点以外的任何地方不相交。
现在请你求出，对于每一个西侧的点，能够沿着边到达多少东侧的点。

输入输出格式

输入格式：
第1行包含4个整数n, m, A, B(1≤n≤300000, 0≤m≤900000,1≤A,B≤109)，
分别表示格丁尼亚市中心的节点数，街道数和岛屿的尺寸。
接下来的n行，每行包含两个整数xi，yi (0≤xi≤A,0≤yi≤B)，表示第i个节点的坐标。任意两个节点的坐标都不相同。
再往下的m行表示街道，每条街道用3个整数ci, di, ki（1≤ci, di≤n, ci≠di, ki∈{1,2}），
表示节点ci、di有街道连接
如果ki=1,表示从ci到di的街道是单向的，否则，这条街道可以双向行驶。每个无序对{ci, di}最多出现1次。
你可以假设西岸节点中至少有1个能够到达东岸的一些节点。

输出格式：
为每个西岸节点输出1行，包括从这个节点出发能够到达东岸的节点数目

输入输出样例

输入样例#1：

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

输出样例#1：

2
0
2

输入样例#2：

12 13 7 9
0 1
0 3
2 2
5 2
7 1
7 4
7 6
7 7
3 5
0 5
0 9
3 9
1 3 2
3 2 1
3 4 1
4 5 1
5 6 1
9 3 1
9 4 1
9 7 1
9 12 2
10 9 1
11 12 1
12 8 1
12 10 1

输出样例#2：

4
4
0
2

说明

$1 \leq n \leq 300000, 0 \leq m \leq 900000, 1 \leq A, B \leq 10^9$

题解

首先显然可以对这个图缩一波强连通分量。注意到题目隐含了一个平面图的条件，对于一个平面图的左侧点，它能到达的右侧点应该在右侧是相邻的一段。因此，我们可以先扔掉那些不可达的右侧点，然后按照$y$坐标的顺序编号，用DFS来计算出缩点后的图中，每一个点对应的右侧区间左右端点，这样就可以计算出答案了。
复杂度$O(n \log n)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 300005;

int n, m, A, B;
std::vector<int> gra[MAXN], gran[MAXN];

typedef std::pair<int, int> PII;
std::vector<int> lft, rgt;
PII node[MAXN];
int id[MAXN];
bool vis[MAXN];

int dfn[MAXN], low[MAXN], clk, sno[MAXN], scc, mx[MAXN], mn[MAXN];
bool insta[MAXN];
std::stack<int> sta;
std::set<PII> edges;

void tarjan(int u) {
    dfn[u] = low[u] = ++clk;
    insta[u] = true; sta.push(u);
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if(insta[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        scc++;
        int p;
        do {
            p = sta.top(); sta.pop();
            insta[p] = false;
            sno[p] = scc;
            if(node[p].first == A) {
                mx[scc] = std::max(mx[scc], id[p]);
                mn[scc] = std::min(mn[scc], id[p]);
            }
        } while(p != u);
    }
}

void dfs(int u) {
    if(vis[u]) return;
    vis[u] = true;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        dfs(v);
    }
}

void dfs_m(int u) {
    if(vis[u]) return;
    vis[u] = true;
    for(int i = 0; i < gran[u].size(); i++) {
        int v = gran[u][i];
        dfs_m(v);
        mx[u] = std::max(mx[u], mx[v]);
        mn[u] = std::min(mn[u], mn[v]);
    }
}

inline bool cmp(int a, int b) {
    return node[a].second > node[b].second;
}

int main() {
    memset(mn, 0x3f, sizeof(mn));
    n = readint(); m = readint(); A = readint(); B = readint();
    for(int i = 1; i <= n; i++) {
        int x = readint(), y = readint();
        if(x == 0) lft.push_back(i);
        if(x == A) rgt.push_back(i);
        node[i] = PII(x, y);
    }
    for(int i = 1, u, v, k; i <= m; i++) {
        u = readint(); v = readint(); k = readint();
        gra[u].push_back(v);
        if(k == 2) gra[v].push_back(u);
    }
    for(int i = 0; i < lft.size(); i++) {
        int u = lft[i];
        dfs(u);
    }
    std::sort(rgt.begin(), rgt.end(), cmp);
    for(int i = 0; i < rgt.size(); i++) {
        int u = rgt[i];
        if(!vis[u]) rgt.erase(rgt.begin() + i), i--;
        else id[u] = i + 1;
    }
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) tarjan(i);
    }
    for(int u = 1; u <= n; u++) {
        for(int i = 0; i < gra[u].size(); i++) {
            int v = gra[u][i];
            if(sno[u] != sno[v] && !edges.count(PII(sno[u], sno[v]))) {
                gran[sno[u]].push_back(sno[v]);
                edges.insert(PII(sno[u], sno[v]));
            }
        }
    }
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= scc; i++) dfs_m(i);
    std::sort(lft.begin(), lft.end(), cmp);
    for(int i = 0; i < lft.size(); i++) {
        int u = lft[i];
        printf("%d\n", std::max(0, mx[sno[u]] - mn[sno[u]] + 1));
    }
    return 0;
}