USACO Section 2.3 Controlling Companies - Xavier's Blog
明明是一道难度不大的题，我却做了N天才做出来，惭愧惭愧！看到题的第一想法就是如果A控制了B，就把B所占有的股份传给A以及A的母公司，并且这样递归下去。可自己编程会发生股份重复计算的情况，解决方法是当将B的股份更新到A上时（通过母公司的关系找到A），如果之前A已经直接或间接控制了B，那么如果再加就算是重复计算了。但在判断A是否直接或间接控制B时，又要判断是否有环。
后来在网上找到了一种解法：当发现A控制B时，将B的股份传给A，如果发现增加股份之后，A中的股份[A][i] > 50 并且A还没有控制i，则将(A, i)加入队列。一直循环操作，直至队列为空为止。
官方的解题报告中，其实就是我一开始想的递归的方法，他在更新（A, B）时：
如果A已经控制B，退出
若没有，control[A][B] = 1
将B的股份传给A
枚举已控制了A的i，递归更新（i, B）
枚举A的股份[A][k]，如果大于50，递归更新（A, k）
Read full article from USACO Section 2.3 Controlling Companies - Xavier's Blog
No comments:
Post a Comment