首页 > Web开发 > 详细

[题解] [JSOI2013] 超立方体

时间:2020-02-10 20:59:48      阅读:61      评论:0      收藏:0      [点我收藏+]

题面

题解

这就是一道模拟题

就是看什么是不符合情况的

一种是点数不对, 一种是点数对了边数不对, 一种是每个点的度数不对, 一种是前三个都对了, 但是你模拟完之后发现两个点的编号相同

排除掉这四种就行

至于模拟, 就你有一个 BFS 层数, 原点为 0 , 你对于一个 BFS 序为 \(i\) 的点, 找到所有的他连接的 BFS 序为 \(i - 1\) 的点, 每一维都或一下就行

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
const int N = 100005;
const int M = 1000005; 
using namespace std;

int T, cnt, num[205], sum[205], vis[N], head[N], d[N], id[N], dis[N], n, m, sz; 
struct edge { int to, nxt; } e[M << 1];
bool flag;
queue<int> q; 

template < typename T >
inline T read()
{
    T x = 0, w = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * w; 
}

inline void adde(int u, int v) { e[++cnt] = (edge) { v, head[u] }, head[u] = cnt; }

void clear()
{
    memset(head, 0, sizeof(head)), memset(d, 0, sizeof(d)), cnt = 0, flag = 1;
    memset(id, -1, sizeof(id)), memset(dis, -1, sizeof(dis)); 
}

int main()
{
    T = read <int> (), num[cnt = 0] = 1; 
    while(num[cnt] < 32768)
    {
    num[cnt + 1] = 2 * num[cnt], cnt++; 
    sum[cnt] = num[cnt - 1] + 2 * sum[cnt - 1]; 
    vis[num[cnt]] = cnt; 
    }
    while(T--)
    {
    clear(); 
    n = read <int> (), m = read <int> (), sz = vis[n]; 
    for(int u, v, i = 1; i <= m; i++)
    {
        u = read <int> (), v = read <int> ();
        adde(u, v), adde(v, u), d[u]++, d[v]++; 
    }
    if(!sz && (n != 1)) { puts("-1"); continue; } 
    if(m != sum[sz]) { puts("-1"); continue; } 
    for(int i = 0; i < n; i++)
        if(d[i] != (sum[sz] * 2) / n) { flag = 0; break; } 
    if(!flag) { puts("-1"); continue; }
    dis[id[0] = 0] = 0, q.push(0), cnt = 0; 
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        if(dis[u] > 1) id[u] = 0; 
        for(int v, i = head[u]; i; i = e[i].nxt)
        {
        v = e[i].to; 
        if(dis[v] == -1)
        {
            dis[v] = dis[u] + 1, q.push(v);
            if(dis[v] == 1) id[v] = num[cnt++]; 
        }
        else if(dis[v] == dis[u] - 1)
            id[u] |= id[v]; 
        }
    }
    for(int i = 0; i < n; i++)
        if(id[i] == -1) { flag = 0; break; }
    if(!flag) { puts("-1"); continue; }
    for(int u = 0; u < n && flag; u++)
        for(int i = head[u]; i; i = e[i].nxt)
        if(id[u] == id[e[i].to]) { flag = 0; break; }
    if(!flag) { puts("-1"); continue; }
    for(int i = 0; i < n; i++)
        printf("%d%c", id[i], i == n - 1 ? '\n' : ' '); 
    }
    return 0; 
}

[题解] [JSOI2013] 超立方体

原文:https://www.cnblogs.com/ztlztl/p/12292457.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!