[USACO10HOL] Cow War G

### 题目描述 给定 $V$ 个点，$E$ 条边的无向图。 一开始每个点上有 `T` 牛，`J` 牛，或者没有（`E`）。 `J` 牛可以 `MOVE` 到一个相邻的点，也可以 `ATTACK` 相邻点上的一个 `T` 牛。不过操作有限制，只能按照 `MOVE`,`ATTACK` 或者 `MOVE` 然后 `ATTACK` 三种方式操作。 一个 `T` 牛仅能被 `ATTACK` 一次，被 `ATTACK` 后它会留在原地。 需要保证任意时刻，每个点上有且仅有一头牛。 求所有 `T` 牛被 `ATTACK` 的最大次数，并给出一个可行的操作方案。 ### 输入格式 第一行两个整数 $V,E$，表示无向图的点数和边数。 接下来一行 $V$ 个字符，第 $i$ 个字符表示第 $i$ 个点的初始状态。 接下来 $E$ 行每行两个整数 $u,v$，表示存在一条连接 $u,v$ 的无向边。 ### 输出格式 第一行一个整数，表示所有 `T` 牛被 `ATTACK` 的最大次数。 接下来若干行，每行以 `MOVE u v` 或 `ATTACK u v` 的形式给出，表示你的操作方案。 ### 说明/提示 对于测试点 $1\sim5$，$1\leq V\leq 30,1\leq E\leq 50$。 对于测试点 $6\sim 10$，$1\leq V\leq 500,1\leq E\leq 2\times 10^3$。 对于测试点 $11\sim 15$，$1\leq V\leq 10^3,1\leq E\leq 5\times 10^3$。 注意：一个操作需要描述现在的位置，例如：点 $3$ 上的牛先 `MOVE` 到点 $2$，再 `ATTACK` 点 $4$，应该写为： \``` MOVE 3 2 ATTACK 2 4 \```

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.

\* 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.

5 4 
TEJTJ 
1 2 
2 3 
3 4 
4 5 

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.