e337: NOIP2018 Day2.3.保卫王国
Tags :
Accepted rate : 1人/2人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-07-22 16:22

Content

Z 国有n座城市,n1条双向道路,每条双向道路连接两座城市,且任意两座城市都能通过若干条道路相互到达。

Z 国的国防部长小 Z 要在城市中驻扎军队。驻扎军队需要满足如下几个条件:

  • 一座城市可以驻扎一支军队,也可以不驻扎军队。
  • 由道路直接连接的两座城市中至少要有一座城市驻扎军队。
  • 在城市里驻扎军队会产生花费,在编号为i的城市中驻扎军队的花费是pi

小 Z 很快就规划出了一种驻扎军队的方案,使总花费最小。但是国王又给小 Z 提出 了m个要求,每个要求规定了其中两座城市是否驻扎军队。小 Z 需要针对每个要求逐一 给出回答。具体而言,如果国王提出的第j个要求能够满足上述驻扎条件(不需要考虑 第 j 个要求之外的其它要求),则需要给出在此要求前提下驻扎军队的最小开销。如果 国王提出的第j个要求无法满足,则需要输出1(1jm)。现在请你来帮助小 Z。

Input

第 1 行包含两个正整数n,m和一个字符串type,分别表示城市数、要求数和数据类型。type是一个由大写字母 AB 或 C 和一个数字 123 组成的字符串。它可以帮助你获得部分分。你可能不需要用到这个参数。这个参数的含义在【数据规模与约定】中有具体的描述。

第 2 行n个整数pi,表示编号i的城市中驻扎军队的花费。

接下来 n1 行,每行两个正整数u,v,表示有一条uv的双向道路。

接下来 m 行,第j行四个整数a,x,b,y(ab),表示第j个要求是在城市a驻扎x支军队, 在城市b驻扎y支军队。其中,x 、 y 的取值只有 0 或 1:若 x 为 0,表示城市 a 不得驻扎军队,若 x 为 1,表示城市 a 必须驻扎军队;若 y为 0,表示城市 b不得驻扎军队, 若 y为 1,表示城市 b 必须驻扎军队。

输入文件中每一行相邻的两个数据之间均用一个空格分隔。

Output

输出共 m 行,每行包含 1 个整数,第j行表示在满足国王第j个要求时的最小开销, 如果无法满足国王的第j个要求,则该行输出 1

Sample Input
5 3 C3 
2 4 1 3 9 
1 5 
5 2 
5 3 
3 4 
1 0 3 0 
2 1 3 1 
1 0 5 0
Sample Output
12 
7 
-1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (4%): 2.0s , <10M
公開 測資點#1 (4%): 2.0s , <1K
公開 測資點#2 (4%): 2.0s , <1K
公開 測資點#3 (4%): 2.0s , <1K
公開 測資點#4 (4%): 2.0s , <1K
公開 測資點#5 (4%): 2.0s , <1M
公開 測資點#6 (4%): 2.0s , <1M
公開 測資點#7 (4%): 2.0s , <1M
公開 測資點#8 (4%): 2.0s , <1M
公開 測資點#9 (4%): 2.0s , <1M
公開 測資點#10 (4%): 2.0s , <1M
公開 測資點#11 (4%): 2.0s , <1M
公開 測資點#12 (4%): 2.0s , <10M
公開 測資點#13 (4%): 2.0s , <10M
公開 測資點#14 (4%): 2.0s , <10M
公開 測資點#15 (4%): 2.0s , <10M
公開 測資點#16 (4%): 2.0s , <10M
公開 測資點#17 (4%): 2.0s , <10M
公開 測資點#18 (4%): 2.0s , <10M
公開 測資點#19 (4%): 2.0s , <10M
公開 測資點#20 (4%): 2.0s , <10M
公開 測資點#21 (4%): 2.0s , <10M
公開 測資點#22 (4%): 2.0s , <10M
公開 測資點#23 (4%): 2.0s , <10M
公開 測資點#24 (4%): 2.0s , <10M
Hint :

对于 100%的数据,n,m100000,1pi100000

测试点编号 type n=
1,2 A3 10
3,4 C3
5,6 A3 100
7 C3
8,9 A3 2×10^3
10,11 C3
12,13 A1 10^5
14∼16 A2
17 A3
18,19 B1
20,21 C1
22 C2
23∼25 C3

数据类型的含义:

A:城市i与城市i+1直接相连。
B:任意城市与城市 1 的距离不超过 100(距离定义为最短路径上边的数量),即如果这 棵树以 1 号城市为根,深度不超过 100
C:在树的形态上无特殊约束。
1:询问时保证a=1,x=1,即要求在城市 1 驻军。对b,y没有限制。
2:询问时保证a,b是相邻的(由一条道路直接连通)
3:在询问上无特殊约束。

Tags:
出處:
NOIP2018提高组Day2第三题 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」