求两道google onsite题目的详细解答~跪谢！！

第一题，如果真是求个最大独立集，可以先把原来的图做个最大二分图匹配（存在多个匹配的话取点加权和最小的），然后这个二分图的补图的点的权值和就是所求了。因为图节点的level总和是不变的，所以一个子图权值最小，其补图的权值就最大。楼主怎么会遇到这么难的题目。。

补充内容 (2018-4-11 04:03):
忽略我，建树然后dp

bambloo 发表于 2018-4-7 06:57
提供一个思路，用hashmap建树，然后用dp做

果然，poj经典题目，nb..

lovedudu 发表于 2018-4-11 03:46
第一题，如果真是求个最大独立集，可以先把原来的图做个最大二分图匹配（存在多个匹配的话取点加权和最小的 ...

house robber iii和这题很像，但是house robber是严格的树，所以dp简单点，但是这题怎么dp？
     G
     /\
   P  P
  / \/  \
c   c    c
这样的情况的话（两个director共享一个下属），要处理的情况很多吧？

bambloo 发表于 2018-4-7 09:12
这就不是环了哥

补充内容 (2018-4-7 09:13):

可是有向无环图的话（譬如下图的情况），能怎么dp呢？
     G
     /\
   P  P
  / \/  \
c   c    c

zbwc 发表于 2018-4-12 10:23
house robber iii和这题很像，但是house robber是严格的树，所以dp简单点，但是这题怎么dp？
     G
   ...

如果考官想考经典题型，不会出现一个人向两个director汇报。如果非要纠结这种情况，可以给每个点加一个id，这样就可以dp了。不过因为结构不再是树，在root-bottom遍历的时候就需要避免出现环和同一个节点重复计算

lovedudu 发表于 2018-4-13 08:00
如果考官想考经典题型，不会出现一个人向两个director汇报。如果非要纠结这种情况，可以给每个点加一个id ...

“避免出现环和同一个节点重复计算”
其实就是这点使得我觉得dp不好做，得按其他算最大独立集的算法走。。希望是我杞人忧天了

不知道说的对不对，

首先我们用connected component labelling 的方法把相互有关联的人都放到同一个组里，同时记录每个人被report的次数，当然你挨个search也行。

因为有level，我们可以做个假设：同级之间不互相report，如果你发现互相report或者还能向下级report的话就比较麻烦了，你要在每个级更新的时候找环，基本和暴力枚举没啥区别了。

下面我们设计一个DP记录：
从级别最低（如果同级可以互相report还能向下级report的话就用report次数最少）的人开始，记录3个东西，1.该人被邀请的话最大得分 2.该人不被邀请的最大得分 3.当前层最大得分的时候（所有人）不能被邀请的次数（这可能是个vector哦,如果能向下report，gg，基本等于记录所有情况吧。。。）
下一层把 被report数+1 的人挨个加进来，更新所有人状态，祈求不要出现得分一样的情况，否则你要把多个相同最高分的情况下每个人不能被邀请的次数都maintain住，根据此人不能被邀请次数是否为0,更新一次总和。

其实我感觉只是弱一点的暴力枚举。



补充内容 (2018-4-13 09:38):
感觉从级别最高的人开始往下dp比较好，记录下一层每个人不能被邀请的次数，恩