首页 > 其他分享 >[CF566E]Restoring Map

[CF566E]Restoring Map

时间:2023-10-30 21:44:52浏览次数:23  
标签:Map CF566E int 样例 叶子 near cities 节点 Restoring

题目描述

Archaeologists found some information about an ancient land of Treeland. We know for sure that the Treeland consisted of $ n $ cities connected by the $ n-1 $ road, such that you can get from each city to any other one along the roads. However, the information about the specific design of roads in Treeland has been lost. The only thing that the archaeologists can use is the preserved information about near cities.

Two cities of Treeland were called near, if it were possible to move from one city to the other one by moving through at most two roads. Also, a city is considered near to itself. During the recent excavations archaeologists found a set of $ n $ notes, each of them represents a list of cities, near to some of the $ n $ cities of the country. However, unfortunately, none of the found records lets you understand in what order the cities go in the list and for which city in the list the near to it cities were listed.

Help the archaeologists and restore any variant of the map of Treeland that meets the found information.

输入格式

The first line contains integer $ n $ ( $ 2<=n<=1000 $ ) — the number of cities in the country.

Next $ n $ lines describe the found lists of near cities. Each list starts from number $ k $ ( $ 1<=k<=n $ ), representing the number of cities in the list followed by $ k $ city numbers. All numbers in each list are distinct.

It is guaranteed that the given information determines at least one possible road map.

输出格式

Print $ n-1 $ pairs of numbers representing the roads of the country. The $ i $ -th line must contain two integers $ a_{i},b_{i} $ ( $ 1<=a_{i},b_{i}<=n $ , $ a_{i}≠b_{i} $ ), showing that there is a road between cities $ a_{i} $ and $ b_{i} $ .

The answer you print must satisfy the description of close cities from the input. You may print the roads of the countries in any order. The cities that are connected by a road may also be printed in any order.

If there are multiple good answers, you may print any of them.

样例 #1

样例输入 #1

5
4 3 2 4 1
5 5 3 2 4 1
5 4 2 1 5 3
4 2 1 4 3
3 1 4 5

样例输出 #1

1 4
1 2
1 3
4 5

样例 #2

样例输入 #2

6
5 6 1 3 4 2
5 2 1 3 4 6
6 3 6 2 5 4 1
6 6 1 2 5 3 4
3 5 2 4
5 3 1 2 4 6

样例输出 #2

2 4
1 2
2 3
2 6
4 5

首先,任何一条连接两个非叶子节点的边,他们一定是某两个集合的交集。

然后用 bitset 暴力就可以得到所有非叶子节点之间的连边。

考虑叶子节点要连到那个点上,首先叶子节点对应的集合一定是包含他的所有集合中大小最小的那个。

叶子节点距离不超过2的店中一定有一个点和其他所有点有连边,用 bitset 找到这个点。

但是要是和一个叶子距离不超过2的只有三个点?那说明有一个点在排除叶子节点的树中是个叶子,找到并和叶子节点相连。

特判菊花图和只有两个非叶子节点的情况。前者直接输出,后者用并查集判断每个叶子节点属于那边。

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,k,s[2],in[N],mn[N],wh[N],fa[N],p[N],m;
vector<int>g[N];
bitset<N>w[N],mp[N],nw;
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
int main()
{
	memset(mn,0x7f,sizeof(mn));
	scanf("%d",&n);
	if(n==2)
	{
		puts("1 2");
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&k);
		g[i].resize(k);
		for(int j=0;j<k;j++)
		{
			scanf("%d",&g[i][j]);
			if(k<mn[g[i][j]])
				mn[g[i][j]]=k,wh[g[i][j]]=i;
			w[i][g[i][j]]=1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			bitset<N>t=w[i]&w[j];
			if(t.count()==2)
			{
				for(int j=t._Find_first(),c=0;j<N;j=t._Find_next(j),++c)
					s[c]=j;
				mp[s[0]][s[1]]=mp[s[1]][s[0]]=1;
				in[s[0]]++,in[s[1]]++;
			}
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(mp[i][j])
				++m,printf("%d %d\n",i,j);
	if(m==1)
	{
		for(int i=1;i<=n;i++)
			if(!in[i])
				fa[i]=i;
		for(int i=1;i<=n;i++)
		{
			if(in[i])
				continue;
			for(int j:g[wh[i]])
				if(!in[j])
					fa[find(j)]=find(i);
		}
		for(int i=1,c=0;i<=n;i++)
			if(!in[i]&&fa[i]==i)
				p[i]=s[c++];
		for(int i=1;i<=n;i++)
			if(!in[i])
				printf("%d %d\n",i,p[find(i)]);
	}
	else if(m)
	{
//		for(int i=1;i<=m;i++)
//			printf("%d %d\n",e[i].first,e[i].second);
		for(int i=1;i<=n;i++)
		{
			if(in[i])
				continue;
			int p=0,c=0;
			for(int j:g[wh[i]])
			{
				if(!in[j])
					continue;
				if(c<2)
					s[c]=j;
				++c;
				nw=mp[j]&w[wh[i]];
				if(nw.count()==1)
					p=nw._Find_first();
			}
			if(c^2)
				printf("%d %d\n",i,p);
			else
				printf("%d %d\n",i,in[s[0]]<in[s[1]]? s[0]:s[1]);
		}
	}
	else
	{
		for(int i=2;i<=n;i++)
			printf("1 %d\n",i);
	}
}

标签:Map,CF566E,int,样例,叶子,near,cities,节点,Restoring
From: https://www.cnblogs.com/mekoszc/p/17798928.html

相关文章

  • 快速编译QCMAP方法
    快速编译QCMAP方法:step1:cd/fibocom/huangguanyuan/sa522/sa525m_le/SA525M_apps/apps_proc/pokystep2:DISTRO=qti-distro-tele-debugMACHINE=sa525msourceqti-conf/set_bb_env.shstep3:bitbakesystemd|tee-abuild_systemd_log.txtbitbakedata|tee-ab......
  • Hadoop三大组件(HDFS,MapReduce,Yarn)
    1、HDFSHDFS是Hadoop分布式文件系统。一个HDFS集群是由一个NameNode和若干个DataNode组成的。其中NameNode作为主服务器,管理文件系统的命名空间和客户端对文件的访问操作;集群中的DataNode管理存储的数据。2、MapReduceMapReduce是一个软件框架,基于该框架能够容易地编写......
  • 2.手写map
    我们首先先创建一个index.js的文件在文件中定义一个数组,就像这样letarray=[10,20,30];array.map((item)=>console.log(item));使用nodeindex.js运行这段代码,我们可以看到输出的结果是102030现在让我们来实现自己的map方法吧letarray=[10,20,30];//与fo......
  • 关于mapStruct-高阶用法
    描诉:符合应用场景的实用的mapStruct对于bean映射的方法1.使用自定义转换器(Converters):如果你需要自定义映射逻辑,可以创建自定义转换器类,并使用@Mapper注解的uses属性来引用它们。这允许你在映射中使用自定义方法,以满足特定需求.@Mapper(uses={CustomConverter.class})public......
  • 按Value对Map进行排序,技术大佬们都在用这个方法
    在Java中,Map的排序一般会根据Key或者Value来进行。按照Value对Map进行排序,通常会用在以下几种场景。1.数据可视化:如果你正在创建一个数据可视化工具,你可能会需要根据数据的值来进行排序。例如,你可能有一个表示员工工资的Map,你想要根据工资值来对员工进行排序,并在图表中展示。2.......
  • Optional.ofNullable()方法, 参数list或者map如果为null执行 ofNullable(创建个新对象
    Optional.ofNullable()方法举个栗子publicstaticvoidmain(String[]args){List<String>list=null;list.forEach(x->System.out.println(x));}工作中经常会遇到,查询返回空,如果没有判空处理,一不小心就会空指针异常。加上if判断处理也可以,但是jdk1.......
  • 信号量Semaphore的使用
    Semaphore是jdk中提供的用来限制资源可以同时被几个线程访问的工具类,它底层也是用aqs实现的。以现实生活中停车场的例子来举例,一个停车场总的车位数是固定的,@Slf4jpublicclassThreadTest4{publicstaticvoidmain(String[]args){//假设只能停两辆车......
  • std::map和std::unordered_map
    区别std::map和std::unordered_map是C++标准库中的两个容器,用于实现键值对的关联。它们之间的主要区别在于底层实现和性能特征。底层实现:std::map是基于红黑树(一种平衡二叉搜索树)实现的有序映射容器,而std::unordered_map是基于哈希表实现的无序映射容器。排序:std::map中的......
  • HashMap集合遍历随机性问题分析
    一、原因分析1.1HashMap对象的遍历HashMap的遍历是通过此类中字段table数组进行顺序遍历,原因如下所示:1#HashMap迭代遍历源码2publicfinalbooleanhasNext(){3returnnext!=null;4}56finalNode<K,V>nextNode(){7Node<K,V>[]t;......
  • 无涯教程-Clojure - struct-map函数
    通过显式定义将哪些值分配给结构中的哪些键,此函数用于将值专门分配给键值。struct-map-语法(struct-mapstructnamekeynvaluen….)参数   - "structname"是要赋予结构的名称,"keyn和valuen"是需要分配给该结构的键值。返回值 - 返回一个结构对象,其值映射......