求助

学术版

ダ月 @ 2022-04-03 00:14:44

有 n 个人在一起玩狼人游戏，游戏中有一些玩家的身份是狼人，剩下玩家的身份是平民。狼人知道彼此之间的身份，而平民对其他人的身份信息一无所知。

天亮时，每名玩家要指证另一名玩家是狼人。狼人一定会做伪证，指证某个平民为狼人，而平民可能指证某个狼人，也可能指证另一个平民。

给定每名玩家的指证对象，请分析场面上最多可能有多少名狼人？注意游戏规定至少需要有一名平民。

有大佬给点思路呗。

by WeLikeStudying @ 2022-04-03 07:22:22

所以似乎就是建图跑最大独立集。

by WeLikeStudying @ 2022-04-03 07:24:14

然后，这个图比较特殊，形成了一棵基环树森林，似乎可以用树形 DP 快速求解？

by Cerisier @ 2022-04-03 07:24:22

@WeLikeStudying 也有可能都不是狼人吧

by WeLikeStudying @ 2022-04-03 07:25:30

@Cerisier 确实，不过前面的结论是对的吗？

by sgweo8ys @ 2022-04-03 07:42:20

每个人向他指证的人连边，这样每个点的出度就是 1，原图构成一棵基环内向树森林

考虑一棵基环内向树，显然一条边的两端不能都是狼人，DP 求最大独立集即可

具体方法：

设 f_{i, 0} 为 i 子树内，i 是平民的最大狼人数，f_{i, 1} 为 i 子树内，i 是狼人的最大狼人数，这样转移显然

将环断掉，考虑环上两个相邻的点 x, y，分别以他们为根进行上面的 DP，最后答案就是 \min(f_{x, 0}, f_{y,0})

注意上述 f_{x, 0} 是以 x 为根的 DP 值，

by sgweo8ys @ 2022-04-03 07:46:14

前面有点没讲清楚，“将环断掉”指断掉 x, y 之间的边

by ダ月 @ 2022-04-08 22:13:48

谢谢各位大佬，此帖终。