我草，忘记复制源码了。
by Usada_Pekora @ 2022-10-21 21:06:33
```
## 题目描述
给定 $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
\```
```
by Usada_Pekora @ 2022-10-21 21:16:38
@[小粉兔](/user/10703) @[离散小波变换°](/user/68344)
by Usada_Pekora @ 2022-10-21 21:18:15
另外本题数据用的是官方的，然而官方的数据最大点只到 $E=2200$，建议加强。
还有这个 SPJ 并没有给出仅答案正确应有的 50% 分。
```#include "testlib.h"
using namespace std;
const int maxn = 1010;
const int maxm = 5010;
const string com[2] = {"ATTACK", "MOVE"};
int n, m;
char mp[maxn];//testdata.in
struct que {
int u;
int v;
} qus[maxm]; //graph storage
struct data {
int v;
int next;
} edge[maxm << 1];
int alist[maxn];
int cnt;
void add(const int &u, const int &v) {
edge[++cnt].v = v;
edge[cnt].next = alist[u];
alist[u] = cnt;
return ;
}
string now;
int anss;
int usrr;//answer compair&&users output
bool ins[maxn];
bool att[maxn];
bool mov[maxn];
int num;
inline bool unicom(const int &a, const int &b) {
for (int next = alist[a]; next; next = edge[next].next)
if (edge[next].v == b)
return true;
else ;
return false;
}
inline bool move(const int &a, const int &b) {
if (!unicom(a, b))
return false;
if (mp[a] == 'J' && mp[b] == 'E' && mov[a] == false && att[a] == false)
mov[a] = true, swap(mp[a], mp[b]), swap(mov[a], mov[b]), swap(att[a], att[b]);
else
return false;
return true;
}
inline int attack(const int &a, const int &b) {
if (!unicom(a, b))
return -1;
if (mp[a] == 'J' && mp[b] == 'T' && att[a] == false) {
if (ins[b] == false) {
ins[b] = true, att[a] = true;
return true;
}
ins[b] = true, att[a] = true;
return 0;
} else
return -1;
}
int a, b;
int pos;
int main(int argc, char *argv[]) {
registerTestlibCmd(argc, argv);
n = inf.readInt();
m = inf.readInt();
char opt = 0;
for (int i = 1; i <= n; i++) {
opt = 0;
while (opt != 'J' && opt != 'E' && opt != 'T')
opt = inf.readChar();
mp[i] = opt;
}
for (int i = 1; i <= m; i++)
qus[i].u = inf.readInt(), qus[i].v = inf.readInt(), add(qus[i].u, qus[i].v), add(qus[i].v, qus[i].u);
anss = ans.readInt();
usrr = ouf.readInt();
if (anss != usrr)
quitf(_wa, "on line 1 cloum 1 expect %d found %d.score:0", anss, usrr);
usrr = 0;
while (usrr != anss) {
now = ouf.readToken();
a = ouf.readInt();
b = ouf.readInt();
if (now == com[0]) {
int qwq = attack(a, b);
if (qwq == -1)
quitp(0.5, "wrong solution,the cow %d can't attack %d", a, b);
else
usrr += qwq;
}
if (now == com[1])
if (!move(a, b))
quitp(0.5, "you cannot move %d to %d", a, b);
}
quitf(_ok, "ok,the answer is correct");
return 0;
}
```
by Usada_Pekora @ 2022-10-21 21:27:06
@[Zyingyzzz](/user/434929) 已添加，感谢您的贡献
by 离散小波变换° @ 2022-10-24 23:05:52
@[chaotic](/user/218250) 不可以，你把我私信关了。
by Usada_Pekora @ 2022-11-04 20:11:12
FHQ 的 `merge(x, y)` 基于 $x,y$ 对应的两个树是值域上不相交的，且 $y$ 对应的更大。
即 $y$ 的最小值大于 $x$ 的最大值。
by Usada_Pekora @ 2022-11-04 20:12:15
这就是为什么必须 `rs[x] = merge(rs[x], y)`或者 `ls[y] = merge(x, ls[y])`。
by Usada_Pekora @ 2022-11-04 20:13:39