# 总算把USACO的受欢迎奶牛做出来了

`3 3`
`1 2`
`2 1`
`2 3`

1

-----------------------------------------------------------------

Egg Pain的我就Egg Pain地写了一个Egg Pain的递归栈模拟，纪念如下

```#include <cstdio>
#include <algorithm>
struct Edge {
int from, to;
Edge* next;
};
const int MAXN = 100001, MAXM = 500001;
struct UFS {
int father[MAXN], rank[MAXN], root(int);
void initialize(int), plus(int, int);
~UFS();
};
struct Cell {
int x;
bool finished, first, visjto;
Edge* j;
void call();
};
int n, m, low[MAXN], dfn[MAXN], nowdfn, stk[MAXN], top, s[MAXN], cst;
bool vis[MAXN], ins[MAXN];
UFS ufs;
Cell cs[MAXN];
int main() {
int cnt = 0, tmp;
freopen("popular.in", "r", stdin);
freopen("popular.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++) {
int s, t;
Edge* tmp = new Edge;
scanf("%d%d", &s, &t);
tmp->from = s;
tmp->to = t;
}
ufs.initialize(n);
for(int i = 1; i <= n; i++) {
if(!vis[i]) {
cst = 1;
cs[cst].x = i;
cs[cst].first = true;
cs[cst].finished = false;
while(cst != 0) {
cs[cst].call();
if(cs[cst].finished) {
cst--;
}
}
}
}
for(int i = 1; i <= n; i++) {
for(Edge* j = head[i]; j != NULL; j = j->next) {
if(ufs.root(i) != ufs.root(j->to)) {
s[ufs.root(i)]++;
}
}
}
for(int i = 1; i <= n; i++) {
if(ufs.root(i) == i && s[i] == 0) {
cnt++;
tmp = i;
}
}
printf("%d\n", cnt == 1 ? ufs.rank[tmp] : 0);
for(int i = 1; i <= n; i++) {
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
void UFS::initialize(int n) {
for(int i = 1; i <= n; i++) {
father[i] = i;
rank[i] = 1;
}
}
int UFS::root(int x) {
return father[x] == x ? x : root(father[x]);
}
void UFS::plus(int x, int y) {
father[y] = x;
rank[x] += rank[y];
}
UFS::~UFS() {
delete[] father;
delete[] rank;
}
void Cell::call() {
if(first) {
nowdfn++;
top++;
dfn[x] = low[x] = nowdfn;
ins[x] = vis[x] = true;
stk[top] = x;
first = false;
}
else {
if(!visjto) {
low[x] = std::min(low[x], low[j->to]);
}
if(ins[j->to]) {
low[x] = std::min(low[x], dfn[j->to]);
}
j = j->next;
}
if(j == NULL) {
if(low[x] == dfn[x]) {
int f = stk[top];
top--;
if(f != x) {
while(true) {
int i = stk[top];
top--;
ufs.plus(f, i);
if(i == x) {
break;
}
}
}
}
finished = true;
}
else {
if(!vis[j->to]) {
cst++;
cs[cst].x = j->to;
cs[cst].first = true;
cs[cst].finished = false;
visjto = false;
}
else {
visjto = true;
}
}
}```

## COGS130. [USACO Mar08] 游荡的奶牛[DP]

130. [USACO Mar08] 游荡的奶牛 ★☆   输入文件:ctravel.in   输出文件:ctravel.out   简单对比时间限制:1 s   内存限制:128 MB 奶牛们在被划分成N行M列(2 <= N <= 100; 2 <= M <= 100)的草地上游走,试图找到整块草地中最美味的牧草.Farmer John在某个时刻看见贝茜在位置(R1, C1),恰好T (0 < T <= 15)秒后,FJ又在位置(R2, C2)与贝茜撞了正着.FJ并不

## 【COGS &amp; USACO】896. 圈奶牛（凸包）

http://cojs.tk/cogs/problem/problem.php?pid=896 我的计算几何入门题... 看了看白书的计算几何部分,,恩好嘛.. 乃们都用向量!!!! 干嘛非要将2个点确定一条线变成一个点从原点o出发的射线!!!! 这就是所谓的玩概念吗 然后用所谓的向量加减,是这些向量起点相同,然后就变成了原点o出发的射线!!! 然后你们还在玩概念!我跪了. (以上纯属蒟蒻吐槽) 好吧,计算几何非常有用的..简化了不少操作. 这里还有啥点积啥叉积.点积就是同一起点的向量(终点)的

## 【题解】晋升者计数 Promotion Counting [USACO 17 JAN] [P3605]

[题解]晋升者计数 Promotion Counting [USACO 17 JAN] [P3605] 奶牛们又一次试图创建一家创业公司,还是没有从过去的经验中吸取教训.!牛是可怕的管理者! [题目描述] 奶牛从 \(1\) ~ \(N(1≤N≤1e5)\) 进行了编号,把公司组织成一棵树,\(1\)号奶牛作为总裁(树的根节点).除总裁以外的每头奶牛都有且仅有唯一的一个的上司(即它在树上的父结点).每一头牛\(i\)都有一个不同的能力指数 \(p(i)\),描述了她对其工作的擅长程度.如果奶牛