世界上有N顶点和M边。有三种类型的边：类型“AB”、“BC”和“CA”。
有 A、B 和 C 三个人。每个人都可以使用一条边当且仅当它的类型名称包含该人的姓名。（例如，A 可以使用 AB 类型和 CA 类型的边）
我想选择一些边，这样对于所有人来说，图形都是连接的。因此，如果我们制作一个由 AB 类型和 CA 类型的边组成的图，则该图应该是连通的。（这也应该适用于 AB/BC、BC/CA 型）
我应该如何解决这个问题？有两个版本
- 如果我想最小化所选边的数量怎么办？
- 如果我想最小化所选边的总成本怎么办？
这是我尝试过的。
主要是，如果它连接 X 和 Y 的两个图，则添加类型为“XY”的边非常好。所以，首先添加所有非常好的边，然后添加一些连接至少一个图的边为一个人。
如果我无限地打乱边缘的顺序，这可能是一个很好的解决方案，但我不确定这一点，它不能解决第二个问题。
我有一些贪婪的策略：首先为 A 制作一个连接图，A 的数量（或成本）最小，然后是 B，然后是 C。打乱人的顺序（因此算法将应用 6 次）
我有一种强烈的感觉，这个问题是 NP-hard，但不能将问题变成众所周知的 NP-hard 问题。