[USACO][Section 2.3][搜索] Controlling Companies

题目大意


有些公司是其他公司的部分拥有者,因为他们获得了其他公司发行的股票的一部分。例如,福特公司拥有马自达公司12%的股票。据说,如果至少满足了以下三个条件之一,公司A就可以控制公司B了:

  • 公司A = 公司B。
  • 公司A拥有大于50%的公司B的股票。
  • 公司A控制K(K >= 1)个公司,记为C1, …, CK,每个公司Ci拥有xi%的公司B的股票,并且x1+ …. + xK > 50%。

给你一个表,每行包括三个数(i,j,p);表明公司i享有公司j的p%的股票。计算所有的数对(h,s),表明公司h控制公司s。至多有100个公司。写一个程序读入N组数(i,j,p),i,j和p是都在范围(1..100)的正整数,并且找出所有的数对(h,s),使得公司h控制公司s。

继续阅读[USACO][Section 2.3][搜索] Controlling Companies

[HDU][3696][搜索] Farm Game

题目大意


农场有n种产品,他们之间可以通过牲畜或机械进行加工转化。转化形式为:1单位的产品A可以转化为x单位的产品B,其中x是大于0的实数。另外,每一种产品有不同的售价,第i种产品的单价为Pi。现给出若干初始产品,请将其经过适当加工转化,然后全部卖出,使得最终获利最大。

继续阅读[HDU][3696][搜索] Farm Game

[POJ][3291][搜索] Destroying the bus stations

描述:

Gabiluso是他国家最厉害的间谍之一。现在他试图去完成一个“不可能”的任务-减缓Colugu市的军队抵达机场的速度。Colugu市有n个车站和m条路。每条路直接连接两个车站,所有的路都是单向的。为了维护空气质量,政府停用了所有军队车辆。所以军队必须乘坐巴士去机场。两个车站之间可能不只一条路。如果一个车站被摧毁,那么所有通向那个车站的道路都没用了。Gabiluso需要去做的是摧毁一些车站使得军队不能在k分钟内赶到机场。一辆巴士通过一条路只需要一分钟。从1到n给所有车站编号。编号为1的车站在军营里,编号为n的车站在机场里。军队总是从编号为1的车站出发。

由于有重兵把守,所以编号为1和n的车站不能被摧毁。当然那里没有一条路直接从1号车站连接到n号车站。

请帮助Gabiluso计算他需要摧毁车站的最小数量,他必须完成任务。

继续阅读[POJ][3291][搜索] Destroying the bus stations