文章目录

• 题意
• 思路

传送门

题意

给你$n$个点，需要给每个点定向，方向可以向右或者向左，定向之后点会朝选择的方向移动，要求满足$m$个条件，两种不同的条件如下：

$i,j$两个位置定向之后移动不会相遇。

$i,j$两个位置定向之后一定会相遇。

如果不能满足输出$NO$，否则输出$YES$，并且给出定向之后的点的方向和位置。

思路

考虑两种情况的方向如何选择，首先他们两个位置一定选择不同的方向，让后根据是否相遇来调整他们的位置。那么根据第一个条件，我们给$i,j$连无向边，那么有解的第一个条件就比较显然了，就是这个构成的图是二分图，让后现在他们的方向确定了，接下来需要确认他们的位置，我们分两种情况来讨论分别对应题目的两种情况：

假设$i$位置取$L$，$j$位置取$R$，由于他们不会相遇，那么$x_i<x_j$。

假设$i$位置取$L$，$j$位置取$R$，由于他们会相遇，那么$x_i>x_j$。

看到大于号，需要跟拓扑序联系起来，那么我们就按照从小到大的位置来填，连边就按照上面的小的连大的，最终判断是否存在环即可。

复杂度$O(n+m)$

#include<bits/stdc++.h> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define Mid (tr[u].l+tr[u].r>>1) #define pb push_back using namespace std;const int N=1000010,INF=0x3f3f3f3f,mod=1e9+7; typedef long long LL;int n,m; vector<int>v[N]; bool flag; int col[N],d[N]; int st[N]; struct Node {int x,y,z; }p[N]; struct node {char ch;int pos; }ans[N];void dfs(int u,int c) {col[u]=c;st[u]=0;for(auto x:v[u]) {if(col[x]) {if(col[x]==c) flag=false;continue;}dfs(x,3-c);} }char get(int pos) {if(col[pos]==0) return 'L';if(col[pos]==1) return 'R';else return 'L'; }void solve() {flag=true;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) {int a,b,c; scanf("%d%d%d",&a,&b,&c);v[b].pb(c);v[c].pb(b);p[i]={a,b,c};}for(int i=1;i<=n;i++) if(!col[i]) dfs(i,1);if(!flag) {puts("NO");return;}for(int i=1;i<=n;i++) v[i].clear();for(int i=1;i<=m;i++) {int x,y,z;x=p[i].x,y=p[i].y,z=p[i].z;if(x==2) {if(col[y]==1) d[z]++,v[y].pb(z);else d[y]++,v[z].pb(y);} else {if(col[y]==2) d[z]++,v[y].pb(z);else d[y]++,v[z].pb(y);}}queue<int>q;int pos=0;for(int i=1;i<=n;i++) if(!d[i]) q.push(i);while(q.size()) {int u=q.front(); q.pop();ans[u]={get(u),pos++};for(auto x:v[u]) {if(--d[x]==0) {q.push(x);}}}for(int i=1;i<=n;i++) if(d[i]) {puts("NO");return;}puts("YES");for(int i=1;i<=n;i++) {printf("%c %d\n",ans[i].ch,ans[i].pos);} }int main() {int _=1;while(_--) {solve();}return 0; }

总结

以上是生活随笔为你收集整理的CF 1635E Cars 二分图 + 拓扑的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。