文章目錄

• 題意
• 思路

傳送門

題意

給你$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 二分图 + 拓扑的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。