题解P6868 [COCI2019-2020#5] Matching

Mo_Han136 · 2021-08-24 19:06:04 · 题解

P6868 [COCI2019-2020#5] Matching

题目描述

给 n 个点，最多存在任意两点的 x 或 y 相等，一条连线只能平行于 x 或 y ，求是否存在一种方案，使得每个点均被连线覆盖，且连线间没有公共点（即不相交）。

题解

如果将所有连线都放入图中（不考虑相交），可以发现只存在两种情况：链和环。

考虑链的情况：

如果链上有奇数个点，显然不存在合法方案，如图。

如果链上有偶数个点，则只存在一种可能合法的方案，即由一端开始相间选择，如图。

而关于环，则有两种可能合法的方案，即全选竖边或全选横边，如图。

（一张图用到底）

题目的关键就在于通过检查边与边是否相交，从而判断链与链、链与环、环与环间的影响，最终得出合法方案。

实现

首先要将链和环找出来。因为图中非链即环，所有基本上没什么细节，很好实现。

...
const int M=1e5+5,T=1e5;
int n,head[M],cnte,cnt,m,rt;
bool vis[M],fl;
vector<int> ax[M],ay[M];
struct node{int x,y;}a[M],tmp,ans[M];
struct edge{int to,nxt;}e[M<<1];
void Add(int x,int y){
    e[++cnte]=(edge){y,head[x]};
    head[x]=cnte;
}
void dfs(int x,int fa){
    vis[rt=x]=1;++cnt;
    erep(i,x){
        int y=e[i].to;
        if(y==fa)continue;
        if(!vis[y])dfs(y,x);
        else fl=1;
    }
}
...
int tot,mk[M];
vector<node> gx,gy,cx[M],cy[M];
void dfs1(int x,int fa,int d){
    erep(i,x){
        int y=e[i].to;if(y==fa)continue;
        if(d){
            if(a[x].x==a[y].x)gx.pb((node){x,y}),Tx.Ins((node){x,y},0);
            if(a[x].y==a[y].y)gy.pb((node){x,y}),Ty.Ins((node){x,y},0);
            ans[++m]=(node){x,y};
        }
        dfs1(y,x,!d);
    }
}
bool vis2[M];
void dfs2(int x,int fa){
    vis2[x]=1;
    erep(i,x){
        int y=e[i].to;if(y==fa)continue;
        if(y!=rt && vis2[y])continue;
        if(a[x].x==a[y].x)cx[tot].pb((node){x,y}),Cx.Ins((node){x,y},tot);
        if(a[x].y==a[y].y)cy[tot].pb((node){x,y}),Cy.Ins((node){x,y},tot);
        if(!vis2[y])dfs2(y,x);
    }
}
...
rep(i,1,n=rd()){
    a[i].x=rd(),a[i].y=rd();
    ax[a[i].x].pb(i);ay[a[i].y].pb(i);
}
rep(i,1,T)if(ax[i].size()==2)Add(ax[i][0],ax[i][1]),Add(ax[i][1],ax[i][0]);
rep(i,1,T)if(ay[i].size()==2)Add(ay[i][0],ay[i][1]),Add(ay[i][1],ay[i][0]);
rep(i,1,n)if(!vis[i]){
    cnt=0;fl=0;dfs(i,0);
    if(cnt&1)return puts("NE"),0;
    if(!fl)dfs1(rt,0,1);
    else ++tot,dfs2(rt,0);
}
...

对于以上代码，大家可能看不懂其中的 Tx、Cx 等，这正是接下来要讲的。

在找出所有链和环的边后，就要判断它们相互之间的影响了。注意到只有横边和竖边会相互制约，因此对于横边 (x_1,x_2,y_1)，可以在区间 [x_1,x_2] 内加入 y_1，而当查询竖边 (x_1,y_1,y_2) 时，对 x_1 单线查询是否有 [y_1,y_2] 内的点。

可以用带 set 的线段树实现上述操作，也就是代码中的 Tx、Cx 等。实现上没什么困难，插入用 insert，查询用 lower_bound，删除用 erase，具体如下：

...
#define lp p<<1
#define rp p<<1|1
set<node>::iterator it;
bool operator < (const node &a,const node &b){return a.y<b.y;}
struct Seg{
    set<node> t[M<<2];
    void chg(int x,int y,node z,int l=1,int r=T,int p=1){
        if(l==x && r==y)return t[p].insert(z),void();
        int mid=(l+r)>>1;
        if(y<=mid)chg(x,y,z,l,mid,lp);
        else if(mid<x)chg(x,y,z,mid+1,r,rp);
        else chg(x,mid,z,l,mid,lp),chg(mid+1,y,z,mid+1,r,rp);
    }
    void era(int x,int y,node z,int l=1,int r=T,int p=1){
        if(l==x && r==y){
            it=t[p].lb(z);
            if(it!=t[p].end() && it->y==z.y)t[p].erase(it);
            return;
        }
        int mid=(l+r)>>1;
        if(y<=mid)era(x,y,z,l,mid,lp);
        else if(mid<x)era(x,y,z,mid+1,r,rp);
        else era(x,mid,z,l,mid,lp),era(mid+1,y,z,mid+1,r,rp);
    }
    node qry(int x,node z,int l=1,int r=T,int p=1){
        it=t[p].lb(z);
        node s=(node){n+1,T+1};
        if(it!=t[p].end())s=*it;
        if(l==r)return s;
        int mid=(l+r)>>1;
        if(x<=mid)return min(s,qry(x,z,l,mid,lp));
        return min(s,qry(x,z,mid+1,r,rp));
    }
    void Ins(node s,int id){
        int x=s.x,y=s.y;
        if(a[x].x==a[y].x)chg(min(a[x].y,a[y].y),max(a[x].y,a[y].y),(node){id,a[x].x});
        if(a[x].y==a[y].y)chg(min(a[x].x,a[y].x),max(a[x].x,a[y].x),(node){id,a[x].y});
    }
    void Era(node s,int id){
        int x=s.x,y=s.y;
        if(a[x].x==a[y].x)era(min(a[x].y,a[y].y),max(a[x].y,a[y].y),(node){id,a[x].x});
        if(a[x].y==a[y].y)era(min(a[x].x,a[y].x),max(a[x].x,a[y].x),(node){id,a[x].y});
    }
}Tx,Ty,Cx,Cy;
...

有了数据结构的支持，接下来就是寻找合法方案了。

首先先寻找链对环的影响。如果链的横边与环的竖边相交，则环的竖边不可用，此时环只有一种可能合法的方案，即横边。为了方便，可以将它当做只有横边方案的链，从环中删除，加入链中，便于与其他环判断。同理竖边与横边也是一样。

...
for(int i=0;i<(int)gx.size();++i){
    int x=gx[i].x,y=gx[i].y;
    int l=min(a[x].y,a[y].y),r=max(a[x].y,a[y].y);
    for(tmp=Cy.qry(a[x].x,(node){0,l});tmp.y<=r;tmp=Cy.qry(a[x].x,(node){0,l})){
        int id=tmp.x;mk[id]=1;
        rep(j,0,cx[id].size()-1)gx.pb(ans[++m]=cx[id][j]),Tx.Ins(cx[id][j],id);
        rep(j,0,cx[id].size()-1)Cx.Era(cx[id][j],id);
        rep(j,0,cy[id].size()-1)Cy.Era(cy[id][j],id);
    }
}
for(int i=0;i<(int)gy.size();++i){
    int x=gy[i].x,y=gy[i].y;
    int l=min(a[x].x,a[y].x),r=max(a[x].x,a[y].x);
    for(tmp=Cx.qry(a[x].y,(node){0,l});tmp.y<=r;tmp=Cx.qry(a[x].y,(node){0,l})){
        int id=tmp.x;mk[id]=1;
        rep(j,0,cy[id].size()-1)gy.pb(ans[++m]=cy[id][j]),Ty.Ins(cy[id][j],id);
        rep(j,0,cx[id].size()-1)Cx.Era(cx[id][j],id);
        rep(j,0,cy[id].size()-1)Cy.Era(cy[id][j],id);
    }
}
...

经过以上操作，我们成功得到了一些唯一方案的链和一些不会被链干扰的环，接下来判断链与链之间是否会相互矛盾，如果矛盾则结束程序。而关于剩下环，因为不受链的干扰，因此只需全部选横边或竖边就不会矛盾。

...
for(int i=0;i<(int)gx.size();++i){
    int x=gx[i].x,y=gx[i].y;
    int l=min(a[x].y,a[y].y),r=max(a[x].y,a[y].y);
    tmp=Ty.qry(a[x].x,(node){0,l});
    if(tmp.y<=r)return puts("NE"),0;
}
for(int i=0;i<(int)gy.size();++i){
    int x=gy[i].x,y=gy[i].y;
    int l=min(a[x].x,a[y].x),r=max(a[x].x,a[y].x);
    tmp=Tx.qry(a[x].y,(node){0,l});
    if(tmp.y<=r)return puts("NE"),0;
}
rep(i,1,tot)if(!mk[i])
    rep(j,0,cx[i].size()-1)ans[++m]=cx[i][j];
puts("DA");
rep(i,1,m)printf("%d %d\n",ans[i].x,ans[i].y);
...

最后放上完整的代码：

#include<bits/stdc++.h>
#define db double
#define reg register
#define LL long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ull unsigned long long
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define erep(i,a) for(int i=head[a];i;i=e[i].nxt)

using namespace std;
bool Handsome;
inline int rd(){
    reg int x=0;reg char o=getchar();reg bool O=0;
    for(;o<48 || 57<o;o=getchar())if(o=='-')O=1;
    for(;48<=o && o<=57;o=getchar())x=(x<<1)+(x<<3)+(o^48);
    return O?-x:x;
}
inline void Mi(int &x,int y){if(x>y && (x=y));}
inline void Mx(int &x,int y){if(x<y && (x=y));}
const int M=1e5+5,T=1e5;
int n,head[M],cnte,cnt,m,rt;
bool vis[M],fl;
vector<int> ax[M],ay[M];
struct node{int x,y;}a[M],tmp,ans[M];
struct edge{int to,nxt;}e[M<<1];
void Add(int x,int y){
    e[++cnte]=(edge){y,head[x]};
    head[x]=cnte;
}
void dfs(int x,int fa){
    vis[rt=x]=1;++cnt;
    erep(i,x){
        int y=e[i].to;
        if(y==fa)continue;
        if(!vis[y])dfs(y,x);
        else fl=1;
    }
}
#define lp p<<1
#define rp p<<1|1
set<node>::iterator it;
bool operator < (const node &a,const node &b){return a.y<b.y;}
struct Seg{
    set<node> t[M<<2];
    void chg(int x,int y,node z,int l=1,int r=T,int p=1){
        if(l==x && r==y)return t[p].insert(z),void();
        int mid=(l+r)>>1;
        if(y<=mid)chg(x,y,z,l,mid,lp);
        else if(mid<x)chg(x,y,z,mid+1,r,rp);
        else chg(x,mid,z,l,mid,lp),chg(mid+1,y,z,mid+1,r,rp);
    }
    void era(int x,int y,node z,int l=1,int r=T,int p=1){
        if(l==x && r==y){
            it=t[p].lb(z);
            if(it!=t[p].end() && it->y==z.y)t[p].erase(it);
            return;
        }
        int mid=(l+r)>>1;
        if(y<=mid)era(x,y,z,l,mid,lp);
        else if(mid<x)era(x,y,z,mid+1,r,rp);
        else era(x,mid,z,l,mid,lp),era(mid+1,y,z,mid+1,r,rp);
    }
    node qry(int x,node z,int l=1,int r=T,int p=1){
        it=t[p].lb(z);
        node s=(node){n+1,T+1};
        if(it!=t[p].end())s=*it;
        if(l==r)return s;
        int mid=(l+r)>>1;
        if(x<=mid)return min(s,qry(x,z,l,mid,lp));
        return min(s,qry(x,z,mid+1,r,rp));
    }
    void Ins(node s,int id){
        int x=s.x,y=s.y;
        if(a[x].x==a[y].x)chg(min(a[x].y,a[y].y),max(a[x].y,a[y].y),(node){id,a[x].x});
        if(a[x].y==a[y].y)chg(min(a[x].x,a[y].x),max(a[x].x,a[y].x),(node){id,a[x].y});
    }
    void Era(node s,int id){
        int x=s.x,y=s.y;
        if(a[x].x==a[y].x)era(min(a[x].y,a[y].y),max(a[x].y,a[y].y),(node){id,a[x].x});
        if(a[x].y==a[y].y)era(min(a[x].x,a[y].x),max(a[x].x,a[y].x),(node){id,a[x].y});
    }
}Tx,Ty,Cx,Cy;
int tot,mk[M];
vector<node> gx,gy,cx[M],cy[M];
void dfs1(int x,int fa,int d){
    erep(i,x){
        int y=e[i].to;if(y==fa)continue;
        if(d){
            if(a[x].x==a[y].x)gx.pb((node){x,y}),Tx.Ins((node){x,y},0);
            if(a[x].y==a[y].y)gy.pb((node){x,y}),Ty.Ins((node){x,y},0);
            ans[++m]=(node){x,y};
        }
        dfs1(y,x,!d);
    }
}
bool vis2[M];
void dfs2(int x,int fa){
    vis2[x]=1;
    erep(i,x){
        int y=e[i].to;if(y==fa)continue;
        if(y!=rt && vis2[y])continue;
        if(a[x].x==a[y].x)cx[tot].pb((node){x,y}),Cx.Ins((node){x,y},tot);
        if(a[x].y==a[y].y)cy[tot].pb((node){x,y}),Cy.Ins((node){x,y},tot);
        if(!vis2[y])dfs2(y,x);
    }
}
bool Most;
int main(){
//  printf("%.2lfMB\n",(&Most-&Handsome)/1024.0/1024.0);
    rep(i,1,n=rd()){
        a[i].x=rd(),a[i].y=rd();
        ax[a[i].x].pb(i);ay[a[i].y].pb(i);
    }
    rep(i,1,T)if(ax[i].size()==2)Add(ax[i][0],ax[i][1]),Add(ax[i][1],ax[i][0]);
    rep(i,1,T)if(ay[i].size()==2)Add(ay[i][0],ay[i][1]),Add(ay[i][1],ay[i][0]);
    rep(i,1,n)if(!vis[i]){
        cnt=0;fl=0;dfs(i,0);
        if(cnt&1)return puts("NE"),0;
        if(!fl)dfs1(rt,0,1);
        else ++tot,dfs2(rt,0);
    }
    for(int i=0;i<(int)gx.size();++i){
        int x=gx[i].x,y=gx[i].y;
        int l=min(a[x].y,a[y].y),r=max(a[x].y,a[y].y);
        for(tmp=Cy.qry(a[x].x,(node){0,l});tmp.y<=r;tmp=Cy.qry(a[x].x,(node){0,l})){
            int id=tmp.x;mk[id]=1;
            rep(j,0,cx[id].size()-1)gx.pb(ans[++m]=cx[id][j]),Tx.Ins(cx[id][j],id);
            rep(j,0,cx[id].size()-1)Cx.Era(cx[id][j],id);
            rep(j,0,cy[id].size()-1)Cy.Era(cy[id][j],id);
        }
    }
    for(int i=0;i<(int)gy.size();++i){
        int x=gy[i].x,y=gy[i].y;
        int l=min(a[x].x,a[y].x),r=max(a[x].x,a[y].x);
        for(tmp=Cx.qry(a[x].y,(node){0,l});tmp.y<=r;tmp=Cx.qry(a[x].y,(node){0,l})){
            int id=tmp.x;mk[id]=1;
            rep(j,0,cy[id].size()-1)gy.pb(ans[++m]=cy[id][j]),Ty.Ins(cy[id][j],id);
            rep(j,0,cx[id].size()-1)Cx.Era(cx[id][j],id);
            rep(j,0,cy[id].size()-1)Cy.Era(cy[id][j],id);
        }
    }
    for(int i=0;i<(int)gx.size();++i){
        int x=gx[i].x,y=gx[i].y;
        int l=min(a[x].y,a[y].y),r=max(a[x].y,a[y].y);
        tmp=Ty.qry(a[x].x,(node){0,l});
        if(tmp.y<=r)return puts("NE"),0;
    }
    for(int i=0;i<(int)gy.size();++i){
        int x=gy[i].x,y=gy[i].y;
        int l=min(a[x].x,a[y].x),r=max(a[x].x,a[y].x);
        tmp=Tx.qry(a[x].y,(node){0,l});
        if(tmp.y<=r)return puts("NE"),0;
    }
    rep(i,1,tot)if(!mk[i])
        rep(j,0,cx[i].size()-1)ans[++m]=cx[i][j];
    puts("DA");
    rep(i,1,m)printf("%d %d\n",ans[i].x,ans[i].y);
    return 0;
}