赤壁之战
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
曹操在赤壁之战中被诸葛亮和周瑜击败，但他并未放弃。由于曹军仍然不擅长水战，他想出了另一个办法：在长江上建造许多岛屿，借助这些岛屿，曹军可以轻松地进攻周瑜的部队。曹操还建造了连接岛屿的桥梁。如果所有岛屿都通过桥梁相连，曹军就能在这些岛屿之间灵活部署。周瑜无法容忍这一点，因此他想摧毁一些桥梁，使至少一个岛屿与其他岛屿分离。但周瑜只剩下一枚诸葛亮留下的炸弹，因此他只能摧毁一座桥梁。周瑜必须派遣携带炸弹的士兵去摧毁桥梁，而桥梁上可能有守卫。轰炸部队的士兵数量不能少于桥梁上的守卫数量，否则任务将失败。请计算周瑜完成岛屿分割任务至少需要派遣多少士兵。
输入格式
输入的测试数据有多组
每组的第一行包含两个正整数和,表示岛屿的数量和桥梁的数量，岛屿的编号分别为。
接下来行表示坐桥梁，每行包括三个整数.表示一座链接岛屿和的桥梁，桥上有名守卫
输出格式
对于每组阳历，输出完成任务需要最小的士兵的数量，如果无法完成任务，则输出-1
3 3
1 2 7
2 3 4
3 1 4
3 2
1 2 7
2 3 4
-1
4
Day1A.割点与割边
- Status
- Done
- Problem
- 18
- Open Since
- 2026-1-26 0:00
- Deadline
- 2026-3-31 23:59
- Extension
- 24 hour(s)