[agc017e]Jigsaw

题目大意

给你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;
        //e=(l,r)
        act[l]=act[r]=1;
        chu[l]++;
        ru[r]++;
        fa[get(l)]=get(r);
    }
    pp=1;
    // neg: in>=out
    fo(i,0,H) if (ru[i]<chu[i]) pp=0;
    // pos: in<=out
    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");
}