ACM东西 - 喂养动物[关闭]-Java 学习之路

-1

有一个ACM问题，我很难解决 . 如果有人能告诉我如何处理它？我真的很感激！

描述为了向主显示你的智慧，你必须按如下方式解决问题：假设有m个人和n个动物 . 如果动物喜欢动物，则可以和平地喂养动物 . 给出一个哪个人喜欢哪个动物的清单，你要确定是否所有动物都可以和平地喂养，条件是每个人最多可以喂k动物 . 输入将有多个测试用例 . 对于每个测试用例，第一行包含两个整数m（1 <= m <= 100）和n（1 <= n <= 100），其中m表示人数，n表示动物数 . 以下行包含m * n 0-1矩阵，表示哪个人喜欢哪个动物 . 如果第i行的第j个元素是1，则第j个动物喜欢第i个人 . 每个测试用例的最后一行包含单个整数k，表示一个人可以喂食的最大动物数量 . 输出对于每个测试用例，如果所有动物都可以平稳喂食则输出“是”，否则输出“否” . 样本输入2 8
1 1 0 1 0 0 1 1
1 1 1 0 1 1 1 1
2
7 2 2
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2
样品输出编号
是

1 回答

2
这可以使用 max-flow problem 来解决 .

创建以下图表：
```
vertices:
V={s,t} U {persons} U {animals}
edges: 
E = { (s,p) | for each p in persons } U
    U {(p,a) | for each person liked by each animal} U 
    U {(a,t) | for each a in animal }
weight function on edges:
w(s,p) = k | for each p in person
w(p,a) = 1 for each p in persons and a in animals
w(a,t) = 1 for
graph:
G  = (V,E,w)
```
现在，您需要在 G 上找到从 s 到 t 的最大整数流 . 这可以使用各种算法解决，如Ford-Fulkerson

达到 t 的流量是喂食的动物数量，解决方案本身由流量给出：
- 如果边缘有一个流量（重量为1） (p,a) - 人 p 喂动物 a .
- 没有人喂食超过 k 只动物，因为可以到达某人的最大流量是 k ，所以不超过 k 可以退出 p .
回复于 2024-05-03T19:14:25+08:00

ACM东西 - 喂养动物[关闭]

1 回答

相关问题