克隆

NC213863. 克隆

描述

作为一名超级英雄，scimoon 每天晚上都要巡视整个城市

这个城市可以抽象成一个 n 个点 m 条边的无向连通图，scimoon 的任务可以看做经过所有的点

尽管 scimoon 是一位非常无敌的英雄，但是人类的能力必然是有极限的：在一个晚上，scimoon 只能经过 $\lceil{\frac{2n}{k}}\rceil$ 个点，并且经过的相邻的两个点之间必须有连边（这些点可以重复）

因此， scimoon 不做人学会了分身术，他可以将自己分身成 k 个，并提早让每个分身来到各自的出发点，同样地，每个分身也只能经过 $\lceil{\frac{2n}{k}}\rceil$ 个点

现在 scimoon 想知道存不存在一种方案使得每个点至少被一个分身经过

输入描述

第一行三个正整数 n,m,k，意义与题目描述中一致

接下来 m 行，每行两个正整数 u,v 表示原图中的一条无向边 (u,v)

输出描述

如果存在解，第一行输出 'YES'（不含引号），接下来输出 k 行，每行先输出一个整数 p，表示这个分身经过的点的数量，接下来按分身经过点的顺序输出 p 个数，表示这个分身经过的点

如果有多解只需要输出一组解

如果不存在点，输出 'NO' 即可（不含引号）

示例1

输入:

3 2 1
2 1
3 1

输出:

YES
4 1 2 1 3

示例2

输入:

输出:

YES
5 1 2 3 2 4
1 5

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 224ms, 内存消耗: 10564K, 提交时间: 2020-11-20 19:17:42

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
int n,m,k;
vector<int> g[N];
bool vis[N];
int a[N<<1],cnt;
void dfs(int u){
	vis[u]=1;a[++cnt]=u;
	for(auto v:g[u]){
		if(vis[v]) continue;
		dfs(v);
		a[++cnt]=u;
	}
}
int main(){
	int i,j;
	cin>>n>>m>>k;
	for(i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1);
	cout<<"YES"<<endl;
	int pos=1;
	for(i=1;i<=k;i++){
		int p=(cnt+k-1)/k;
		if(pos+p-1>cnt) p=cnt-pos+1;
		cout<<p<<" ";
		while(p--) cout<<a[pos++]<<" ";
		cout<<endl;
	}
	return 0;
}

上一题

下一题

详情