水蓝络合物的博客

题目大意

有\(n\)辆车在\(x\)轴整数上，它们要么向左要么向右行驶。 题目会给出\(m\)条关系: * \(1,x,y\): 表示\(x,y\)这两辆车无论速度如何，不可能相遇 * \(2,x,y\): 表示\(x,y\)这两辆车在某些特定速度下，有可能相遇 题目链接

\(2 \le n \le 2 * 10^5,2 \le m \le 2 * 10^5\) 若可以满足，给出每个汽车的坐标和移动方向。

思路

关系\(1,2\)都意味着两辆车的移动方向相反。 * 关系\(1\):两辆车相向而行 * 关系\(2\):两辆车相背而行

所以我们先用二分图来判定是否可以把所有车的方向确定下来。

如果在\(1,x,y\)中\(x\)向左行驶，那么\(y\)就向右行驶，且\(x\)在\(y\)的左边,那么我们就在新的图中建立一条边\(x \rightarrow y\)。其它情况可以类比这种操作。

如何判断关系能否被满足？只需在新的图中跑一遍\(拓扑排序\)即可！

代码

#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int maxN = 2e5 + 7;

int n, m, color[maxN], vis[maxN], d[maxN], ind[maxN];
vector<int> e[maxN], G[maxN];
bool succ;

struct op {
    int op, x, y;
}a[maxN];

void dfs(int x, int col)
{
    if(!succ)
        return ;
    color[x] = col; vis[x] = 1;
    for(int i = 0; i < e[x].size(); ++i) {
        int y = e[x][i];
        if(vis[y] && color[y] == col) {
            succ = false;
            return ;
        }
        else if(vis[y])
            continue;
        dfs(y, col ^ 1);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &a[i].op, &a[i].x, &a[i].y);
        e[a[i].x].push_back(a[i].y);
        e[a[i].y].push_back(a[i].x);
    }
    succ = true;
    for(int i = 1; i <= n; ++i) {
        if(!succ)
            break;
        if(!vis[i])
            dfs(i, 1);
    }
    if(!succ) {
        printf("NO\n");
        return 0;
    }
    for(int i =1; i <= m; ++i) {
        if(a[i].op == 1) {
            if(color[a[i].x] == 1)
                G[a[i].x].push_back(a[i].y), d[a[i].y]++;
            else 
                G[a[i].y].push_back(a[i].x), d[a[i].x]++;
        }
        else {
            if(color[a[i].x] == 1)
                G[a[i].y].push_back(a[i].x), d[a[i].x]++;
            else
                G[a[i].x].push_back(a[i].y), d[a[i].y]++;
        }
    }
    queue<int> q;
    int cnt = 0;
    for(int i = 1; i <= n; ++i)
        if(d[i] == 0)
            q.push(i);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        ind[x] = ++cnt;
        for(int i = 0; i < G[x].size(); ++i) {
            int y = G[x][i];
            d[y]--;
            if(d[y] == 0)
                q.push(y);
        }
    }
    if(cnt != n)
        printf("NO\n");
    else {
        printf("YES\n");
        for(int i = 1; i <= n; ++i) 
            printf("%c %d\n", color[i] == 1? 'L' : 'R', ind[i]);

    }
    return 0;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/03/01/cf1635E/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！