#1755. 同构判定鸡

    ID: 1755 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1092来源:qoj.ac数据:公开样例构造

同构判定鸡

同构判定鸡

题目描述

标题: 同构判定鸡 - Problem - QOJ.ac

#5413. 同构判定鸡

Statistics

The problem was used in the following contests:

北大餐饮综合楼开业了!

小 F 是一只有学识的鸡,为了不被餐饮综合楼四楼的小火锅涮掉,它打算向愚蠢的人类展示一些技能。

人类总共有 T 次询问,每一次给了一张 n 个点 m 条边的图 H=(VH,EH)。而小 F,同构判定鸡,每一次会回答一张图 G=(VG,HG),满足以下条件:

  1. 点数 |VG|≤N;
  2. 边数 |EG|≥M;
  3. H 不是 G 的子图,即:无法通过删除 G 的点和边并重新标号后得到 H。

人类不知道小 F 的高超的图同构水平,于是给定的图 H 会满足一些特殊性质(见数据范围)。

而小 F 觉得这题太简单了,于是把问题交给了你。

输入格式

第一行两个非负整数 T,type,表示数据组数和测试点的序号。若 type=0,则表示该组数据为样例,不会出现在评测数据集合中。也就是说对于所有评测数据,满足 1≤type≤6。

对于每一组数据,第一行 n,m 两个非负整数,含义同题面。

接下来 m 行,每行两个整数 ui,vi,表示图 H 中的一条边。保证没有重边和自环。

最后一行两个整数 N,M,表示对图 G 的点数和边数的限制。

输出格式

对于每一组数据,第一行两个正整数 n′,m′,表示你构造的图 G 的点数和边数。

接着有 m′ 行,每行两个正整数 xi,yi 表示图 G 中的边。

你需要保证图 G 中不存在重边与自环,否则你的答案会被判定为错误。

样例数据

样例输入

1 0
4 3
1 2
1 3
3 4
4 0

样例输出

4 0

样例解释

显然 H 不是空图 G 的子图。

数据范围

本题共 6 个测试点,以下为每个测试点的信息:

测试点 1 到测试点 4 使用 special judge 1 进行测评,输出应完全符合题目条件才能得到所有的分数。

测试点 1(5%):H 为 3 个点的完全图;N≤100,M=[N2/4]。[] 为下取整符号,下同。

测试点 2(10%):H 为完全图,且 n≤10;n≤N≤100,M=[(1−1n−1)⋅N2/2]−1。

测试点 3(10%):H 为 K(2,2)(左侧 2 个点、右侧 2 个点的完全二分图,下同);50≤N≤2000,M=2N。

测试点 4(15%):H 为 K(2,2);N≤2000,且 N 能表示成一个奇质数的平方,M=[N(N−1)/2]。

测试点 5 和测试点 6 满足 T=1,使用 special judge 2 进行测评。输出应完全符合题目条件才能得分。假设你给出的方案的边数为 m′,你程序的得分为 ⌊30×(1−0.5(3Mm′−1))⌋。也就是说,只有 m′≥3M 的方案才能拿到满分。

测试点 5(30%):H 为 K(2,2);N=2850,M=24300,3M=72900;

测试点 6(30%):H 为 K(3,3);N=343=73,M=2350,3M=7050。

对于所有测试点,有 1≤T≤10,N≥n>2。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1 0
4 3
1 2
1 3
3 4
4 0
4 0