P2974 [USACO10HOL]牛的战争Cow War

    • 1通过
    • 23提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 最大流 费用流 USACO 2010 Special Judge 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    Farmer John has long had a dispute with neighbor Farmer Tom over a group of V (1 <= V <= 1,000) pastures conveniently numbered 1..V. Both farmers currently graze their cows on the pastures; each pasture might be empty or might have a single cow which is owned by either Farmer John or Farmer Tom.

    Farmer John's patience is at an end, and he wishes to settle the dispute with Farmer Tom by tipping over Tom's cows. Of course, he wants to strike first and to tip as many of Farmer Tom's cows as possible.

    A total of E (1 <= E <= 5,000) bidirectional cowpaths connect pairs of pastures. No two pastures are connected by more than one cowpath; each path connects exactly two distinct pastures. Paths are described by their endpoints P1_i and P2_i (1 <= P1_i <= V; 1 <= P2_i <= V).

    During his offense, each of Farmer John's cows can traverse a single cowpath if she wishes. Whether or not she chooses to traverse a cowpath, she can then (if she wishes) launch a cow tipping attack to a pasture connected to her pasture by a single cowpath, thus tipping the enemy cow on that pasture. Note that a cow can move and then attack -- but she is not able to attack and then move.

    Each pasture can hold exactly one cow at a time; no cow can move to a pasture occupied by another cow, especially if it has been tipped. Of course, if a pasture is vacated, another cow can later move in to take its place. A tipped cow cannot be tipped again.

    Farmer John wants to know two things:

    * How many of Farmer Tom's cows he can tip in the first salvo

    of the war

    * How to command his cows to move and attack so as to tip

    that maximal number of Farmer Tom's cows in that first salvo

    Find the maximum number of cows that can be tipped and construct a sequence of move and attack commands to his cows that then obey the rules and tip that number of cows. Any such sequence is acceptable, as long as it tips the maximum number of Farmer Tom's cows.

    Consider, for instance, a group of 5 pastures arranged in a line, with each pasture connected (via '--'; see diagram below) to its left and right neighbors (if they exist). In other words, there is a cowpath from Pasture 1 to Pasture 2, Pasture 2 to Pasture 3, etc. Farmer Tom ('T') has 2 cows, standing on pastures 1 and 4, while Farmer John ('J') has 2 cows standing on pastures 3 and 5 ('E' means empty):

    1 2 3 4 5

    T -- E -- J -- T -- J

    In this case, Farmer John can tip both of Farmer Tom's cows by first moving his cow on Pasture 3 to Pasture 2, so that the pastures in order are now TJETJ. Farmer John can then have both of his cows attack to the left. Note that although the cow in Pasture 3 could have attacked to the right without moving, the rightmost cow would then be unable to attack. The only valid solutions thus have the same move and attacks, although the order in which Farmer John commands his cows can vary slightly.

    If you compute the correct maximum number but do not provide a sequence (or your sequence is wrong), you will get 50% of the points for that test case. A program will grade your output.

    Partial feedback will be provided for your first 50 submissions.

    有n个点,m条边的无向图。

    上面的点一开始要么是J牛,要么是T牛,要么是E,表示没有牛。

    然后J牛有两种选择:

    1、直接攻击自己附近的一只T牛,然后停住永远不动。

    2、向邻近的点走一步,然后攻击or不攻击附近的一只T牛,然后停住永远不动。

    特别得,

    J牛不能跑进任何一只本身有牛的点。

    T牛不会动。并且只能被打死一次。然后就算他死了,J牛也不能进入他的领土(他的灵魂开无敌了)!!!

    然后他们动都有先后顺序,然后问最多能打死多少只T牛。

    输入输出格式

    输入格式:

    * Line 1: Two space separated integers: V and E

    * Line 2: A string of V characters (no spaces); character #i indicates whether pasture #i is empty ('E') or has a cow owned by Farmer John ('J') or Farmer Tom ('T')

    * Lines 3..E+2: Line i+2 contains two space separated integers: P1_i and P2_i

    输出格式:

    * Line 1: A single integer, the maximum number of enemy cows Farmer John can have tipped

    * Lines 2.....: One of Farmer John's instructions to his cows (to be executed in the order given):

    MOVE A B

    or ATTACK A B

    where A is the vertex the cow occupies before taking the action and B is the vertex it is moving to or attacking, respectively. Note that when instructing a cow that has already moved to attack, the instruction specifies the location the cow is currently standing, not where it was originally.

    输入输出样例

    输入样例#1: 复制
    5 4 
    TEJTJ 
    1 2 
    2 3 
    3 4 
    4 5 
    
    输出样例#1: 复制
    2 
    MOVE 3 2 
    ATTACK 2 1 
    ATTACK 5 4 
    

    说明

    The other valid outputs are:

    2 MOVE 3 2

    ATTACK 5 4

    ATTACK 2 1

    and 2 ATTACK 5 4

    MOVE 3 2

    ATTACK 2 1

    which are just reorderings of the output shown. This might not be true on other testdata.

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