题目描述

题目:滴翠亭杨妃戏彩蝶,埋香冢飞燕泣残红(题目名 - -)

花谢花飞花满天,红消香断有谁怜?

   游丝软系飘春榭,落絮轻沾扑绣帘。

   闺中女儿惜春暮,愁绪满怀无释处;

   手把花锄出绣帘,忍踏落花来复去。

   柳丝榆荚自芳菲,不管桃飘与李飞;

   桃李明年能再发,明年闺中知有谁?

   三月香巢已垒成,梁间燕子太无情。

   明年花发虽可啄,却不道人去梁空巢也倾。

   一年三百六十日,风刀霜剑严相逼;

   明媚鲜妍能几时,一朝漂泊难寻觅。

   花开易见落难寻,阶前愁煞葬花人;

   独倚花锄泪暗洒,洒上空枝见血痕。

   杜鹃无语正黄昏,荷锄归去掩重门;

   青灯照壁人初睡,冷雨敲窗被未温。

   怪奴底事倍伤神?半为怜春半恼春:

   怜春忽至恼忽去,至又无言去不闻。

   昨宵庭外悲歌发,知是花魂与鸟魂?

   花魂鸟魂总难留,鸟自无言花自羞;

   愿奴胁下生双翼,随花飞到天尽头。

   天尽头,何处有香丘?

   未若锦囊收艳骨,一抔净土掩风流;

   质本洁来还洁去,强于污淖陷渠沟。

   尔今死去侬收葬,未卜侬身何日丧?

   侬今葬花人笑痴,他年葬侬知是谁?

   试看春残花渐落,便是红颜老死时;

一朝春尽红颜老,花落人亡两不知!

林MM刚刚吟诵完这首旷古奇诗,只见宝玉笑吟吟的走了过来。

“啊呀,你来了!正好帮我埋花!”

“…”宝玉心里暗暗叫苦:最近为什么杯具的事情这么多?

林MM的花堆可以近似的看作一个图,图上的每个节点都有一个权值,表示这堆花中共有多少朵花。由于Zrp发明了超时空瞬移器,所以林MM和宝玉可以立刻出现在他们想要到达的花堆并埋葬那堆花中的每一朵。然后,由于超时空瞬移器毕竟不够成熟,所以它启动时的巨大气浪会把与当前这堆花相邻的所有花全部吹散,于是就“花开易见落难寻”同时也没办法“随花飞到天尽头”了。为了不“愁煞葬花人”,宝玉想要设计一个方案,使他和林MM埋掉的花的总数最多。

这时,神牛们提出了抗议:“这不是传说中的NP-HARD最大权独立子图吗?!@#¥%……&×”于是,好心的林MM就又加了一条规定:那些花排成的形状一定是如下的:

1. 这些花堆中的一部分排成了一个环。

2. 这些花堆其余的部分都是一些度为一的点且只与环上的花堆相连。

这下,宝玉开心了:这题太水哩,你要是连这题都做不出那就太××了!

数据范围:

10%的数据保证n<=10。

30%的数据保证n<=1000。

100%的数据保证n<=100000且答案不超过maxlongint

10%的数据保证,整个图仅有一个环而并没有附着在环上的点。

100%的数据保证满足题目中的性质且图中的环的长度大于或等于3

输入格式

输入的第一行包括两个数n,m表示总共有n堆花,m个连接关系(其实m的大小已经由n决定了)

下面m行,每行两个数i,j,表示编号i与j的花堆相邻。

最后一行n个数,第i个数表示编号为i的花堆中花的个数。

输出格式

输出仅包含一个数,表示最多采到的花朵数

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论