一、作家俱乐部(The Writer's Club, Africa/Middle East-Arab and North Africa 2007, LA4091)一个网站上有许多作家,每个作家都被许多读者所喜欢。如果一个读者喜欢一个作家,他也有可能同时喜欢这个作家喜欢的其他作家的作品。例如,如果作家John喜欢Alice写的书,那么喜欢John的读者也有可能喜欢Alice的书。进一步来说,网站希望给喜欢John的读者推荐Alice以及Alice喜欢的作家及Alice喜欢的作家喜欢的作家,如此等等。当然不能给读者推荐已经喜欢的作家。输入T(T<100000)个读者以及N个作家(N≤100),以及喜欢每个作家的人的姓名。根据这些数据,计算出需要将每个作家分别推荐给哪些读者,输出这些读者的姓名。
二、我想我会给自己买个足球队(Think I'll Buy Me a Football Team, Africa/Middle East-Arab and North Africa 2008, LA4367)银行之间会有一些循环债务,如图4.4(a)就显示了4个银行A~D之间的循环债务,A欠B50,B欠A150等,总共需要380来还清银行间所有的债务。
但是仔细观察可以发现,380里面有许多实际上是被浪费的,可以采用如下策略优化:(1)C欠D和D欠A的一样,等于说C欠A是30,把D排除出去。(2)但是A欠C 100,所以可以说A欠C 70。(3)AB之间可以简化成B欠A100。这样就把图4.4(a)简化成图4.4(b),总共需要190(减少了190,也就是50%)。(4)可以继续优化,B还100给A,A还70给C,B可以直接还70给C(不用还100而是30给A)。这样120就可以把所有债务还清,共节省了260也就是68%。给出N(N<1000)个银行中任意两者的债务关系。输出在优化前后还清所有债务各自需要多少钱。