codeforces 1635E-Cars （二分图染色+拓扑排序）

传送门

$difficult:2200$

题意

数轴上存在 $n$ 辆车和 $m$ 个限制，每个限制以 $op$、$u$、$v$ 的形式表示，其中：

$op=1$，则 $u$、$v$ 不论在该数轴上以何种速度行驶，都不会相遇

$op=2$，则 $u$、$v$ 不论在该数轴上以何种速度行驶，都一定相遇

判断是否存在方案满足所有限制，并构造每辆车的行驶方向和初始位置

---

容易想到，不论两辆车间存在何种限制，它们的行驶方向一定相反，当 $op=1$ 时相背而行， $op=2$ 时相向而行，因此可先进行二分图染色判断合法性。

$op=1$ 时，$pos[L]<pos[R]$；$op=2$ 时，$pos[L]>pos[R]$。在同一限制条件下，让 $pos$ 较小指向 $pos$ 较大的，新建有向图跑拓扑排序。

注意如果在拓扑排序中出现环，同样无解。

参考代码

#include 
using namespace std;
#define int long long
#define PII pair<int, int>

const int N = 2e5 + 10;
vector<int> h[N], g[N];
int col[N], in[N], pos[N];
bool vis[N];
int flag = 0, cnt = 0, dis = 0;

struct node {
    int u, v, op;
} ed;
vector<node> edge;

priority_queue<int> q;
int n;
void topsort() {
    while (q.size()) {
        int now = q.top();
        q.pop();
        pos[now] = dis++;
        cnt++;
        for (auto x : g[now]) {
            in[x]--;
            if (in[x] == 0)
                q.push(x);
        }
    }
    if (cnt != n)
        flag = 1;
}

void dfs(int u, int fa, int color) {
    if (flag)
        return;
    vis[u] = 1;
    col[u] = color;
    for (auto v : h[u]) {
        if (v == fa)
            continue;
        if (vis[v] == 1 && col[v] == col[u]) {
            flag = 1;
            return;
        }
        if (vis[v] == 1)
            continue;
        dfs(v, u, color ^ 1);
    }
}

void solve() {
    int m;
    cin >> n >> m;
    while (m--) {
        int op, u, v;
        cin >> op >> u >> v;
        h[u].push_back(v);
        h[v].push_back(u);
        ed.u = u, ed.v = v, ed.op = op;
        edge.push_back(ed);
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i])
            dfs(i, 0, 0);
    }
    if (flag) {
        cout << "NO" << endl;
        return;
    }
    flag = 0;
    for (auto now : edge) {  //新有向图
        int u = now.u, v = now.v, op = now.op;
        if (op == 1) {
            if (col[u] == 0)
                g[u].push_back(v), in[v]++;
            else
                g[v].push_back(u), in[u]++;
        } else if (op == 2) {
            if (col[u] == 0)
                g[v].push_back(u), in[u]++;
            else
                g[u].push_back(v), in[v]++;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) {
            q.push(i);
        }
    }
    topsort();
    if (flag) {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
    for (int i = 1; i <= n; i++) {
        if (col[i] == 0)
            cout << "L ";
        else if (col[i] == 1)
            cout << "R ";
        cout << pos[i] << endl;
    }
}

signed main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

/*
200000 1
2 92734 60628
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120