中山纪念中学 2019年2月 寒假作业 出题 (即将施工完成!!!)

声明


    此题为本人原创,也未参考任何资料。

    意思可能会有点绕 ,标程也不(hai)大(mei)会(xie)写(wan)。

    若大佬们秒切后觉得简单勿喷。如果有什么问题敬请谅解,提出即可。


删点难题

 

Time Limits: 1000 ms    Memory Limits: 131072 KB

  Description

    

    神(Shen)犇(Ben)小 H 有个神奇的草稿本,现在 TA 把它拿出来,并给你画了一个由 n 个点, m 条边构成的无向图(可以有重边,无自环)。此时,TA 要求你删去其中 k 个点,并规定删去编号为 x 的点的分数为:x 点的权值*与点 x 点相连的另一端点未被删掉的边的数量,总分数 为删掉 k 个点的分数之和 与109+7取模 的结果。

    但是因为小 H 非常皮,TA 打算要在你算答案的过程中,擅自删掉 a 个点(不算在总分数内),并修改 b 个点的权值。

    由于神犇小 H 太强了!TA 又在你删点时给你加了个 DEbuff:如果你删掉某个点的分数是小 H 的幸运数 h 的倍数的话,小 H 就会大发雷霆,拿走你这个点的分数!

    现在 TA 将问你 s 次:在 TA 的很多次操作后,如果 让你删去 k 个点(如果点 不够删,则输出 “Error!”, 引号不用输出),最大总分数是多少?不知道聪明的你能否回答 TA 的问题呢?


  Input

  

    第 1 行:三个用空格隔开的数 n,m,k,意义见题面。

    第 2 行:n 个正整数,第i个数 w [ i ] 表示节点 i 的权值(点由 1 ~ n 编号)。

    第 3 ~ m + 2 行:每行两个正整数 x,y,表示从节点 x 到节点 y 有一条相连的无向边。

    第 m + 3 行:四个整数 a,b,h,s 。a,b 的意义见题面,h 代表小 H 的幸运数,s 表示小 H 将询问你 s 次答案。

      接下来 a+b+s 行每行包含 1 或 2 或 3 个数,具体如下:

        格式 1:  1,p,q    含义:将节点 p 的权值改为 q;

        格式 2: 2,p         含义:删掉节点 p;

        格式 3: 3              含义:输出在当前被小 H 暗中操作过后的的无向图中删去 k 个数的最大总分数(如果点 不够删,则输出 “Error!”)。


  Output

    

    共s行,每行仅包含一个整数或 “Error!”,即每次询问的结果。

    注意: 每次询问时小 H 问的问题是 如果 让你删 k 个点,并不是真正的删!!!


  Sample Input

    5  4  2

    1  2  3  4  5

    2  1

    5  3

    3  4

    1  3   

    4  3  3  4

    3

    2  2

    1  4  9

    3

    1   1  100

    1   5  12

    2   1

    3

    2  3

    2  5

    3


  Sample Output

    11

    14

    0

    Error!


  样例解释:

    第一次删 4、5 号节点,有最大总分数为: 4*1+5*1=9 。(如果删 3 号节点就能得到 3*3=9 的分数但是小 H 的幸运数 h 的倍数会被拿掉!)

      注意:像这样如果 总分数 是 h 的倍数 总分数 是不会被拿走的,因为小 H 只在意你 每次删点时 的分数是否是 h 的倍数。

    第二次删 1、5 号节点,有最大总分数为: 1*1+5*1=6 。(同理如果删 3 或 4 号节点都分别能得到 3*3=9*1=9 的分数但会被拿掉!)

    第三次询问时剩 3、4、5 号节点,无论删哪两个点,删点的分数都为小 H 的幸运数 3 的倍数,全部被小 H 拿走,最大总分数为 0 。

    第四次询问时仅剩 4 号节点,不够删,输出 “Error!”。


  Data Constraint

  

    对于前  % 的数据,

    


    标程未出炉(本人觉得挺难调的),于是数据范围和输入输出数据还没造。

     样例输出是手算的,也具有不确定性 (大 [ jue ] 概 [ dui ] 是正确的)!!!

     总之,就提供一个题目,后面的数据等 标程和样例输入输出 确定了再造 ~~~

原文地址:https://www.cnblogs.com/t-s-y/p/10380666.html