题解：CF27D Ring Road 2

William2022 · 2025-08-10 16:29:47 · 题解

入手

如果两条道路被放在同一侧（同为环内或环外）且它们的端点区间相互交叉，就会产生冲突，此时必须将它们分配到不同侧，这是一个约束关系。
我们需要枚举每对有约束的边对并尝试满足全部的约束。

解法

将所有有约束的两条边的边号连上，然后通过染色的方法匹配二分图即可。
复杂度为 O(m^2)

程序设计

我使用了 intersect() 函数来判断是否有约束关系。

#include<bits/stdc++.h>
using namespace std;
const int N=105;

int n,m;

struct Edge{
    int l,r;
}e[N];

bool intersect(const Edge &a,const Edge &b){// 两条非环边是否不能安排在同一侧
    bool A=(a.l<b.l && b.l<a.r);
    bool B=(a.l<b.r && b.r<a.r);
    bool C=(a.l<=b.l && b.l<=a.r);
    bool D=(a.l<=b.r && b.r<=a.r);

    return (A && !D) || (B && !C);
}
vector<int> to[N];
int col[N];

bool dfs(int u){// 匹配二分图
    for(int v:to[u]){
        if(col[v]){
            if(col[v]+col[u]!=3)return 1;
        }else{
            col[v]=3-col[u];
            if(dfs(v))return 1;
        }
    }
    return 0;
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);

    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int l,r; cin>>l>>r;
        if(r<l)swap(l,r);
        e[i]={l,r};
    }

    for(int i=1;i<=m;i++){
        for(int j=i+1;j<=m;j++){
            if(intersect(e[i],e[j])){
                to[i].push_back(j);
                to[j].push_back(i);
            }
        }
    }

    for(int i=1;i<=m;i++){
        if(!col[i]){
            col[i]=1;
            if(dfs(i)){cout<<"Impossible";return 0;}
        }
    }
    for(int i=1;i<=m;i++)cout<<" io"[col[i]];
}