【CF566E】Restoring Map

这个题只要记住,确定非叶子节点就不停枚举两个点,看他们的neith集合是不是只有两个交点,这两个交点之间连边。剩下的细节代码里有。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

struct edge
{
    int x, y;
}e[1010];

int n, lx, ly, lz, ta;

const int ms = 1024;

bitset <ms> neith[ms], mo[ms], mmp[ms], tmp, flag, vis, leaf;

inline int ask(bitset <ms> a)//查询最低位的1
{
    int l = 1, r = n;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        (a & mo[mid]).any() ? r = mid : l = mid + 1;
    }
    return l;
}

int main()
{
    re(n);
    for(ri i = 1; i <= n; i ++)
        mo[i] = mo[i - 1], mo[i].set(i);//让i这一位变成1
    for(ri i = 1; i <= n; i ++)
    {
        mmp[i].set(i), re(lx);
        for(ri j = 1; j <= lx; j ++)
            re(ly), neith[i].set(ly);
    }
    for(ri i = 1; i <= n; i ++)
        for(ri j = i + 1; j <= n; j ++)
            if((tmp = (neith[i] & neith[j])).count() == 2)
            {
                lx = ask(tmp), tmp.reset(lx), ly = ask(tmp);//reset是删除这一位的1
                if(!mmp[lx][ly])
                    flag[lx] = flag[ly] = mmp[lx][ly] = mmp[ly][lx] = vis[lx] = vis[ly] = 1, e[++ ta] = (edge){lx, ly};
            }
    if(vis.none())
        for(ri i = 2; i <= n; i ++)
            printf("1 %d\n", i);
    else
    {
        for(ri i = 1; i <= n; i ++)
            for(ri j = 1; j <= n; j ++)
                if((tmp = (neith[i] & neith[j])) == neith[i] && tmp != neith[j])
                    leaf.set(j);//判断儿子
        for(ri i = 1; i <= n; i ++)
            if(!leaf[i])
            {
                lx = ask(neith[i] ^ (vis & neith[i]));//找出编号最小的没用过的叶子节点
                vis[lx] = 1, tmp = flag & neith[i];
                if(tmp.count() == 2)//如果只有i和另外一个点,也就说剩下的与i联通的都是叶子
                {
                    ly = ask(tmp), tmp.reset(ly), lz = ask(tmp);
                    if(mmp[ly].count() == 2 && mmp[lz].count() == 2)//如果这俩点目前连出去的边都就一条,剩下的点都是叶子
                    {
                        tmp = neith[i] ^ (neith[i] & flag);//找出与自己直接连接的那些叶子
                        for(ri j = 1; j <= n; j ++)
                            if(j != ly && j != lz)
                                if(tmp[j])
                                    printf("%d %d\n", ly, j);
                                else
                                    printf("%d %d\n", lz, j);
                        printf("%d %d\n", ly, lz);
                        return 0;
                    }
                    else
                        e[++ ta] = (edge){mmp[ly].count() == 2 ? ly : lz, lx};//2是靠叶子的一段
                }
                else
                {
                    while(tmp.any())
                    {
                        ly = ask(tmp);
                        if(mmp[ly] == (flag & neith[i]))//如果i能到达的非叶子节点和ly一样
                        {
                            e[++ ta] = (edge){lx, ly}; break;
                        }
                        tmp.reset(ly);
                    }
                }
            }
        for(ri i = 1; i <= ta; i ++)
            printf("%d %d\n", e[i].x, e[i].y);
    }
    system("pause");
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注