带花树模板

#include<bits/stdc++.h>
using namespace std;
const int N=1001;
struct ty
{
    int next, t;
}edge[N*N];
int fa[N],col[N],match[N],vis[N],last[N],n,m,M,head[N],x[N],y[N],L;
//next[i]  存的是i在bfs中沿着非匹配边走到的上一个点
int tmp = 0;
queue<int> q;
void addedge(int x, int y)
{
    edge[++M]=(ty){head[x], y};
    head[x] = M;
}
int findfa(int x)
{
    return fa[x] == x ? x : fa[x] = findfa(fa[x]);
}
int lca(int x, int y) //求环顶
{
    tmp++; //为了不清vis数组，让每次进入函数的时候给vis赋的值都不一样就可以了
    while(1)
    {
        if(x != 0)
        {
            x = findfa(x); //先去x的环顶
            if(vis[x] == tmp) return x;//x走过了，说明已经是环顶了，返回
            vis[x] = tmp; //标记走过
            if(match[x]) x = last[match[x]]; //我往上跳一条匹配边和非匹配边（BFS一层是走了一条匹配边和一条非匹配边）
            else x = 0;
        }
        swap(x, y); //交换xy
    }
}
void flower(int a,int r) //缩环（的一半）
{
    while(a != r)
    {
        int b = match[a], c = last[b]; //a是黑点所以先跳匹配边然后再跳非匹配边
        if(findfa(c) != r) last[c] = b; //因为奇环里到底怎么匹配还不知道，干脆把原来的匹配边也记录一组非匹配边（这样之后就能利用last做任意相邻两个的匹配了）
        if(col[b] == 2) q.push(b), col[b] = 1;
        if(col[c] == 2) q.push(c), col[c] = 1;  //环上的白点要变成黑点（之前本来是交错的黑白，但是直接一个判断就不用关心哪个位置黑哪个位置白了）
        fa[findfa(a)] = findfa(b);
        fa[findfa(b)] = findfa(c);  //并查集维护父亲
        a = c;  //往上跳
    }
}
int work(int s)
{
    for(int i = 1; i <= n; i++)
        last[i] = col[i] = vis[i] = 0, fa[i] = i;  //清数组
    while(!q.empty()) q.pop();
    col[s] = 1;//给起点标成黑色
    q.push(s);
    while(!q.empty())   //广搜
    {
        int x = q.front();
        q.pop();
        for(int i = head[x]; i > 0; i = edge[i].next)
        {
            int y = edge[i].t;
            if(match[x] == y) continue;  //走的匹配边(走回去了)
            if(findfa(x) == findfa(y)) continue; //两个点在同一个已经缩过的奇环里
            if(col[y] == 2) continue; //偶环
            if(col[y] == 1)  //黑点——奇环
            {
                int r = lca(x, y);  //r是环顶
                if(findfa(x) != r) last[x]=y;
                if(findfa(y) != r) last[y]=x;  //xy都是靠非匹配边接在一起的
                flower(x, r);
                flower(y, r);  //缩花，每次缩掉花的一半
            }
            else if(!match[y]) //else表示col等于0——在这次增广中y没访问过；match为0，这个点是个为匹配的点——增广路已经求到了
            {
                last[y] = x;  //y通过非匹配边和x连到一起
                for(int u = y;u != 0;)  //顺着交错路走回去
                {
                    int v = last[u];  //last是他通过非匹配边连的上一个点
                    int w = match[v]; //去v原来匹配的点
                    match[v] = u;
                    match[u] = v;     //匹配边和非匹配边交换——所以uv成为新的一对
                    u = w;    //再从被“抛弃”的那个点开始往前走直到把这个增广路的修改修改完
                    //这里之所以没有改last的值是因为用过了就没用了，后面会退出work函数，再次进入就清空了
                }
                return 1;  //本次增广已经找到增广路了
            }
            else //col等于0——在这次增广中y没访问过，且y原来有匹配
            {
                last[y] = x; //通过未匹配边的y的前一个点为x
                col[y] = 2; //y自己是白点
                col[match[y]] = 1; //y通过匹配边连的前一个点是黑点
                q.push(match[y]);  //这个黑点入队
            }
        }
    }
    return 0;
}
void init(){
    memset(match, 0, sizeof(match));
    memset(head, 0, sizeof(head));
    M = 0;
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &x[i], &y[i]);
    scanf("%d", &L);
    for(int i = 1; i <= n; i++)
    for(int j = i+1; j <= n; j++)
    {
        if(abs(x[i]-x[j]) + abs(y[i]-y[j]) <= L) {addedge(i, j); addedge(j, i);}
    }
    for(int i = 1; i <= n; i++)
    {
        if(!match[i])
        {
            if(!work(i))
            {
                cout<<"NO\n";
                return;
            }
        }
    }
    cout<<"YES\n";
}
int main()
{
    while(scanf("%d", &n) != EOF)
    init();
    return 0;
}