题目大意
给你n块积木，每块积木由三列构成，每块中间那列最长，为固定的H；对于每一块i，左边一列底部会比中间底部高c[i]，然后长度为a[i]，右边类似地,d[i],b[i]. 现在要求你把积木拼接起来，使得所有积木中列底部在同一水平线上，左右两列要么在这条水平线上，要么紧贴着另一块积木某一侧的顶端。 判断是否能够这样拼。 n≤1e5，H≤200，a,b>0，a+c,b+d≤H.
解题思路
我们发现，当一块积木c>0的时候，a的取值没有用。类似地有d,b，那么我们可以把积木分个类。 对于一块积木，若c=0,令l=a,否则l=-c；若d=0,令r=-b,否则r=d；我们称这块积木的类型为(l,r)。 图论转化：连有向边l->r，那么一个合法的拼接是一条路径，而且起点s>0，终点t<0。 那么我们现在要判断，对于一幅包含-H…-1和1…H的图，是否能够拆分成若干段这样的路径。 那么要满足条件： 1，对于i>0,in[i]<=out[i]； 2，对于i<0,in[i]>=out[i]； 3，对于一个弱联通分量，必须有一个点满足in[i]≠out[i]； 前两个条件很显然，后一个条件保证了你在构造真实解的时候，可以把不小心弄出来的环和其他的路径合并，最终构造出合法解。
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define fo(i,j,k) for(i=j;i<=k;i++)
#define fd(i,j,k) for(i=j;i>=k;i--)
#define cmax(a,b) (a=(a>b)?a:b)
#define cmin(a,b) (a=(a<b)?a:b)
typedef long long ll;
const int N=
1e6+
5,M=
2e6+
5,mo=
998244353;
int fa[N],n,H,A,B,C,D,i,pp,pd[N],chu[N],ru[N],l,r,act[N];
int get(
int x)
{
if (fa[x]==x)
return x;
return fa[x]=get(fa[x]);
}
int main()
{
scanf(
"%d %d\n",&n,&H);
fo(i,
0,H*
2) fa[i]=i;
fo(i,
1,n)
{
scanf(
"%d %d %d %d",&A,&B,&C,&D);
if (!C) l=A;
else l=-C;
if (!D) r=-B;
else r=D;
l+=H;
r+=H;
act[l]=act[r]=
1;
chu[l]++;
ru[r]++;
fa[get(l)]=get(r);
}
pp=
1;
fo(i,
0,H)
if (ru[i]<chu[i]) pp=
0;
fo(i,H+
1,
2*H)
if (ru[i]>chu[i]) pp=
0;
fo(i,
0,
2*H) pd[get(i)]|=(ru[i]!=chu[i]);
pd[H]=
1;
fo(i,
0,
2*H)
if (act[i]&&!pd[get(i)]) pp=
0;
if (pp)
printf(
"YES");
else
printf(
"NO");
}
