UVA1292 Strategic game

    • 143通过
    • 392提交
  • 题目来源 UVA 1292
  • 评测方式 RemoteJudge
  • 标签 二分图 最大匹配 背包
  • 难度 提高+/省选-
  • 时空限制 3000ms / 0MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目:策略游戏

    描述:

    Bob非常享受玩电脑游戏的过程,尤其是策略游戏,但是在有些时候,他因为不能在第一时间找到最佳的策略而十分伤心。 现在,他遇到了一个问题。他必须保卫一个中世纪的城市,有很多道路将整个城市连起来,整体上看上去像一棵树。Bob需要放置尽可能少的士兵,保卫树上所有的边。士兵只能放在节点上,但是却可以保卫所有与这个节点相邻的边。

    输入格式:

    输入包含了多组数据。每组数据用以下的方式描述了一棵树。

    第一行包含一个整数n,代表节点总个数。

    每一个节点的描述如下:

    -节点编号(子树个数):子树1....子树子树个数

    或者

    -节点编号(0).

    节点的编号从0到n-1.对于n个(0 < n ≤ 1500)所有的节点而言,每一条边仅在输入数据中出现一次。

    输出格式:每组数据一行,一个整数代表最少放置的士兵个数。

    感谢@Mickey_snow 提供翻译

    题目描述

    PDF

    输入输出格式

    输入格式:

    输出格式:

    输入输出样例

    暂无测试点
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。