15011418730 LV 7 @ 2025-8-24 22:24:45

自动搬运

来自洛谷，原作者为

	Mo_Han136 努力的尽头，没有奇迹

搬运于2025-08-24 22:24:45，当前版本为作者最后更新于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;
}

$\mathcal{By}\quad\mathcal{Most}\ \mathcal{Handsome}$

$\mathcal{2021.08.24}$

ID

5500

时间

2000ms

内存

512MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

题目描述

题解

实现

[COCI 2019/2020 #5] Matching

信息

1 条题解

自动搬运

以下是正文

题目描述

题解

实现

[COCI 2019/2020 #5] Matching

信息

还没有账户？

登录