题解：P9001 [CEOI 2022] Parking

cike_bilibili · 2025-09-19 18:51:31 · 题解

被 ad-hoc 吓晕了。

首先将已经匹配好的位置筛掉，没用。

我们考虑这样去构造一张图，就是说将那些满的栈中上位车颜色向下位车颜色连一条边，容易发现每一个点的度数至多为 2，这启示我们将链和环分开来看。

当然我们要先看孤立点，如果一个点是孤立点那么这个点的两辆车一定在不同位置，并且其上位都没车，直接将两个栈合并即可，这样一定优因为不仅搞定了一个颜色而且留出了一个空栈。

考虑一条链，不妨设有一条链是 1 \to 2 \to 3 \to 4，我们可以画出图：

我们发现当一个点出度为 1 入度为 0，我们可以直接将其合并，这样一来在这条链上下一个元素由于其上面的元素被拿开，就像图中的颜色 2 就被解锁了，这样一直合并就可以直接将链合并，并且不依赖其他空栈。

但是我们容易发现一条链不一定是单向的，他还有可能是像 1 \gets 2 \to 3 \gets 4 \to 5 这样的，中间会有出度为 2 的点，我们可以找到一个出度为 2 的点，显然两辆车都在上位，将其移到一个空栈上，这样就划分成了两个新链了，这样从左往右依次断开出度为 2 的点并处理单向链就行了，只需要一个空栈并且搞完一个链就能还回去。

接下来是环，向上文一样，如果是单向环，我们自然可以断开一条边使其变成单向链，需要一个空栈。

如果有出度为 2 的点，则需要将其断开，具体而言就是出度为 2 的两辆车一定在上位，将其共同移到一个空栈里面，这样就变成了一个链了。

如此构造，其实直接按每条链搞一下就行了，但好像不是很好写。

我们可以直接用栈维护孤立点，出度为 1 且入度为 0 的点，单向环的节点和出度为 2 且入度为 0 的点，按上述优先级弹出然后将能到达的点更新出入度后再重新压入栈内即可。

贴个代码吧但大概率不可读。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
namespace Yukina{
    inline int read(){
        int ans=0,w=1;
        char ch=getchar();
        while(ch<48||ch>57){
           if(ch=='-')w=-1;
           ch=getchar();
        }
        while(ch>=48&&ch<=57){
           ans=(ans<<1)+(ans<<3)+ch-48;
           ch=getchar();
        }
        return w*ans;
    }
    vector<pair<int,int> >ans;
    bool hv[200005];
    int n,m;
    int b[200005],t[200005];
    int r[200005],c[200005];
    int i1[200005],i2[200005];
    int nxt[200005];
    queue<int>s;
    stack<int>q1,q2,q3,q4;
    void clear(){
        while(q1.size()&&(hv[q1.top()]||r[q1.top()]!=0||c[q1.top()]!=0))q1.pop();
        while(q2.size()&&(hv[q2.top()]||r[q2.top()]!=0||c[q2.top()]!=1))q2.pop();
        while(q3.size()&&(hv[q3.top()]||r[q3.top()]!=0||c[q3.top()]!=2))q3.pop();
    }
    void insert(int x){
        if(!x||hv[x])return;
        if(r[x]==0&&c[x]==0)q1.push(x);
        if(r[x]==0&&c[x]==1)q2.push(x);
        if(r[x]==0&&c[x]==2)q3.push(x);
    }
    void move(int x,int y){
        if(t[x]){
            --r[b[x]],--c[t[x]];
            if(b[y])t[y]=t[x],++c[t[y]],++r[b[y]];
            else b[y]=t[x];
            t[x]=0;
            insert(t[x]),insert(b[x]),insert(t[y]),insert(b[y]);

        }else{
            if(b[y])t[y]=b[x],++c[t[y]],++r[b[y]];
            else b[y]=b[x];
            b[x]=0;
            insert(t[x]),insert(b[x]),insert(t[y]),insert(b[y]);
        }
        ans.push_back({x,y});
    }
    struct edge{
        int to;
        int next;
    }ed[400005];
    int cnt;
    int h[200005];
    void add(int x,int y){
        ed[++cnt]={y,h[x]};
        h[x]=cnt;
    }
    bool vis[200005],is[200005],iis[200005];
    int all=0;
    void dfs(int x,int fa){
        is[x]=1;
        for(int i=h[x];i;i=ed[i].next){
            int v=ed[i].to;
            if(is[v])continue;
            dfs(v,x);
        }
    }
    void get(int x,int fa){
        iis[x]=1;
        insert(x);
        for(int i=h[x];i;i=ed[i].next){
            int v=ed[i].to;
            if(iis[v])continue;
            get(v,x);
        }
    }
    signed main(){
        freopen("parking.in","r",stdin);
        freopen("parking.out","w",stdout);
        n=read(),m=read();
        for(int i=1;i<=m;i++)b[i]=read(),t[i]=read();
        for(int i=1;i<=m;i++){
            if(t[i]&&b[i]&&t[i]==b[i]){
                hv[t[i]]=1;
                continue;
            }
            if(!t[i]&&!b[i])s.push(i);
            if(t[i])++r[b[i]],++c[t[i]],add(t[i],b[i]),add(b[i],t[i]),nxt[t[i]]=b[i];
            if(b[i]){
                if(i1[b[i]])i2[b[i]]=i;
                else i1[b[i]]=i;
            }
            if(t[i]){
                if(i1[t[i]])i2[t[i]]=i;
                else i1[t[i]]=i;
            }
        }
        for(int i=1;i<=n;i++){
            if(!is[i]&&!hv[i]&&c[i]+r[i]==1)dfs(i,0);
        }
        for(int i=1;i<=n;i++){
            int now=i;
            if(vis[i]||r[i]!=1||c[i]!=1)continue;
            int cnt=0;
            while(!vis[now]){
                ++cnt;
                vis[now]=1;
                now=nxt[now];
                if(r[now]!=1||c[now]!=1)break;
            }
            if(now==i)q4.push(i);
        }
        for(int i=1;i<=n;i++)if(!is[i]&&!iis[i])get(i,0);
        for(int i=1;i<=n;i++)if(is[i]&&!iis[i])get(i,0);
        while(1){
            clear();
            if(q1.size()){
                int x=q1.top();
                q1.pop();
                move(i1[x],i2[x]);
                s.push(i1[x]);
                hv[x]=1;
                continue;
            }
            if(q2.size()){
                int x=q2.top();
                q2.pop();
                if(t[i1[x]]==x){
                    move(i1[x],i2[x]);
                }else{
                    move(i2[x],i1[x]);
                }
                hv[x]=1;//这个颜色搞完了
                continue;
            }
            if(q4.size()){//拆环

                if(!s.size()){
                    cout<<-1<<'\n';
                    return 0;
                }
                int x=q4.top();
                q4.pop();
                int pos=s.front();
                s.pop();
                if(t[i1[x]]==x)move(i1[x],pos),i1[x]=pos;
                else move(i2[x],pos),i2[x]=pos;
                continue;
            }
            if(q3.size()){
                if(!s.size()){
                    cout<<-1<<'\n';
                    return 0;
                }
                int x=q3.top();
                q3.pop();
                int pos=s.front();
                s.pop();
                move(i1[x],pos),move(i2[x],pos);
                hv[x]=1;
                continue;
            }
            break;
        }
        cout<<ans.size()<<'\n';
        for(pair<int,int> p:ans)cout<<p.first<<' '<<p.second<<'\n';
        return 0;
    }
}
signed main(){
    Yukina::main();
    return 0;
}