web analytics

BZOJ1601[Usaco2008 Oct]灌水(MST+优秀建图)

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1601

分析:

刚开始想的先用MST跑一遍之后树形DP。

但是发现树形DP对与选择水源和链接水源还是有一定障碍.

发现其实在这里问题可以用MST的一个性质.

最小生成树是包含所有点的生成树.

所以为了表示水源.

我们可以建一个超级源点来表示水源.

这样可以完美的解决这个问题.

这样就保证了绝对有水源.

Post a Comment

You must be logged in to post a comment.