F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 3291. -- Alice与能源计划

3291: Alice与能源计划

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 187  Solved: 86
[Submit][Status][Discuss]

Description

在梦境中,Alice来到了火星。不知为何,转眼间Alice被任命为火星能源部长,并立刻面临着一个严峻的考验。为
了方便,我们可以将火星抽象成平面,并建立平面直角坐标系。火星上一共有N个居民点。每个居民点认为是平面
上的一个点。第i个居民点的坐标为(Xi,Yi),对能源的需求量为Poweri。每个居民点消耗的能源由它附近的发电
站提供。由于技术原因,一个居民点消耗的所有能源必须来自同一座发电站。自人类移民火星之初,政府就有一个
规模宏大的发电站建设计划。按照这个计划,政府将在火星上建立M座发电站,这M座发电站将是火星居民的全部能
量来源。其中,第i座发电站的坐标为(xi,yi),产生能量的上限值为Limiti,建设费用为Pricei。同样由于技术原
因,第i座发电站只能为与它的距离不超过Ri的居民点提供能源。然而,由于政府的财政状况一直十分紧张,截至
目前,这M座发电站中只有少量建成并投入使用,多数的发电站尚未开始建设。Alice的任务是修改这个计划,使得
它更符合实际情况。根据新的规定,一座发电站产生的所有能源必须提供给同一个居民点。Alice知道这个规定意
味着N个居民点消耗的能源将分别由N座不同的发电站提供,而且为第i个居民点提供能源的那座发电站的Limit值一
定不小于Poweri。Alice需要在原计划的M座发电站中选择恰好N座发电站,并完全放弃剩余的M-N座发电站,使得这
N座发电站能够满足N个居民点的需要。对于一个可行的方案,设方案中选择的N座发电站构成集合S,而已经建成的
发电站构成集合T,那么定义这个方案的代价为即,一个方案的代价等于被选择的且尚未建成的发电站的建设费用
之和加上没有被选择的且已经建成的发电站的建设费用之和。在所有可行方案中,你必须帮助Alice找到代价最小
的方案,并将选择的N座发电站按编号从小到大的顺序输出。如果代价最小的方案不唯一,则输出其中字典序最小
的方案。
注意,输入文件包含多组测试数据。

Input

第一行包含一个正整数T,表示有T组测试数据。接下来依次是T组测试数据。
每组测试数据的第一行包含两个整数N、M。
接下来N行,每行3个整数:Xi、Yi、Poweri。
再接下来M行,每行6个整数:xi、yi、Limiti、Pricei、Ri、Finishedi。
若Finishedi=1,表示第i座发电站已经建成;否则Finishedi=0,表示第i座发电站尚未开始建设。
1≤N≤400,1≤M≤500,1≤T≤10,0≤xi,yi,Xi,Yi,Pricei≤10000,
1≤Ri,Poweri,Limiti≤10000。不同的居民点或发电站的坐标有可能重合。
关于方案的字典序的大小关系的说明:
设方案A选择的N座发电站的编号从小到大依次为A1,A2,…,AN;
设方案B选择的N座发电站的编号从小到大依次为B1,B2,…,BN。
我们称方案A比方案B字典序更小,当且仅当存在正整数i,满足1≤i≤N,
使得对任意1≤k≤i-1有Ak=Bk,且Ai<Bi。

Output

对于每组测试数据:
若存在可行方案则输出两行。第一行为一个整数,表示最小代价;
第二行是若干个递增的整数,表示字典序最小的最优方案选择的发电站的编号。
若不存在可行方案,则仅输出一行为一个整数-1。

Sample Input

4
1 1
4 4 1
8 7 1 2 5 1
2 3
0 0 3
2 0 2
1 1 5 1 3 0
1 0 5 1 1 1
3 0 5 1 3 0
2 3
0 0 3
2 0 2
1 1 2 0 3 0
1 0 1 0 1 1
3 0 3 0 2 0
2 3
0 0 3
2 0 2
1 1 4 2 2 0
1 0 2 9 1 1
3 0 5 4 2 1

Sample Output

0
1
1
1 2
-1
6
1 2
样例说明
第1组测试数据:
只有一个居民点,其坐标为(4,4),能源需求量Power1=1;仅一座发电站,其坐标为(8,7),产生的能量上限Limit1
=1,建设费用Price1=2,服务范围半径R1=5,Finished1=1表示已经建成。
两个点之间的距离等于5不超过R1,并且Power1≤Limit1。因此唯一的可行方案是花费0的代价保留1号发电站,使
它为1号居民点提供能源。
第2组测试数据:任意选择两个发电站都是一个可行方案。最小代价是1,对应的方案有两种:选择1号和2号发电站;选择2号和3号发电站。而前者的字典序更小。
第3组测试数据:不存在可行方案。
第4组测试数据:代价最小的方案唯一:选择1号和2号发电站,代价为6。

HINT

Source

[Submit][Status][Discuss]

HOME Back