#P6914. nmd

    ID: 6745 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>难度分类省选/NOI-构造与建模图构造分块构造奇偶性分析对称性分析计算几何Pick 定理组合数学鸽巢原理枚举与搜索回溯搜索可行性剪枝估价下界剪枝CF3000

nmd

Problem.A (nmd.cpp)

时间限制:1s

空间限制:512MB

题目描述

给你一个n×mn \times m的点阵,点阵相邻两行和相邻两列之间距离均为 11,你需要在这 nmn m 个点之间连上一些线段,使得这张图满足以下条件:

  1. 每个点的度数恰好为dd,即对于每个点都有恰好dd 条线段与它相连

  2. 每条线段都不经过除了端点以外的点,且任意两条线段之间除端点外不相交。

例如你有一个3×33 \times3 的点阵,则你不能以 (1,1)( 1 , 1 ) 和 (3,3)( 3 , 3 ) 为端点连一条线段,因为这条线段经过了 (2,2)( 2 , 2 );你也不能同时连接分别以 (1,1)( 1 , 1 )、(2,2)( 2 , 2 ) 和 (2,1)(2,1)、(1,2)(1,2) 为端点的两条线段,因为这两条线段在除端点外的地方相交。当 d=2d=2 时,满足上述条件的一种连法在样例解释一中已经给出,同时这种连法是所有连法中线段长度之和最小的。

你需要使这张图的线段长度之和尽量小并输出方案,或指出不存在合法的连线段方案。

为方便你理解这道题的题意以及调试这道题,在下发文件中有一个check.cpp,它会返回你的程序所给出的解是否合法。使用方式是先输入三个正整数n,m,dn , m , d,再按照输出描述输入你的解,check.cpp会返回你的错误信息或返回你的解的长度。若你没有按上述格式输入你的解,则不保证程序能正确运行。

输入描述

输入第一行一个整数TT,表示数据组数。

接下来TT 行,每行包含三个正整数n,m,dn , m , d,其中nn 表示点阵的行数,mm 表示点阵的列数, dd 表示点阵中每个点的度数。

输出描述

对于每一组数据,若没有合法的连线段方案则仅输出一行一个数 −1- 1,否则:

第一行输出你连的线段数cntc n t,接下来 cntc n t 行,每行四个正整数 x1,y1,x2,y2x 1 , y 1 , x 2 , y 2,表示你连了一条以 (x1,y1)( x 1 , y 1 ) 和 (x2,y2)( x 2 , y 2 ) 为端点的线段。(x,y)( x , y ) 表示这个点阵中第xx 行第yy 列的点,例如点阵的左上角被表示为 (1,1)( 1 , 1 ),点阵的右下角被表示为 (n,m)( n , m )。

样例输入一

1
3 3 2

样例输出一

9
1 1 2 1
2 1 3 1
1 1 2 2
1 2 2 2
1 2 1 3
1 3 2 3
2 3 3 3
3 1 3 2
3 2 3 3

样例解释一

原题示意图

可以证明这是线段长度之和最小的解,线段长度之和为8+28+\sqrt{2}。

样例输入二

1
4 4 3

样例输出二

24
1 1 1 2
1 2 1 3
1 3 1 4
4 1 4 2
4 2 4 3
4 3 4 4
1 2 2 2
2 1 2 2
1 1 2 2
3 1 3 2
3 2 4 2
4 1 3 2
1 3 2 3
2 3 2 4
2 3 1 4
3 3 3 4
3 3 4 3
3 3 4 4
1 1 2 1
2 1 3 1
3 1 4 1
1 4 2 4
2 4 3 4
3 4 4 4

样例解释二

原题示意图

可以证明这是线段长度之和最小的解,线段长度之和为20+422 0+4 \sqrt{2}。

样例输入三

1
4 4 4

样例输出三

-1

样例解释三

可以证明不存在合法解。

评分方式

对于每个测试点中的每一组数据,若你的程序没有正确判断解的存在性,或输出的图不满足题目中所给的两个条件, 则你在该组数据获得 00 分,否则令xx 表示你的程序给出的图的线段长度之和与所有合法解中最小的线段长度之和的差,则你在该测试点获得的分数将评定为 ⌊52x⌋\lfloor{\frac{5} {2^{x}}} \rfloor。

你所获得的这个测试点的分数即为该测试点内每组数据的分数的最小值。

限制与约定

对于所有测试点,1≤T≤1501\le T\le150,1≤∑nm≤100001\le\sum nm\le10000,1≤n,m≤1001\le n,m\le100,1≤d≤81\le d\le8。

测试点编号 n,m≤n,m\le d≤d\le
1—4 5 8
5—6 100 1
7—9 2
10—13 3
14—16 5
17—20 8