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

题目描述:

有一些奶牛,其中某些奶牛受其他奶牛欢迎。每头奶牛都喜欢自己,同时都追随它喜欢奶牛的爱好。如果A喜欢B,而B喜欢C,那么A也会喜欢C。如果所有人都喜欢某头奶牛,那么这头奶牛就称之为绝对奶牛。

现在有N头奶牛,同时告诉你M条A喜欢B的信息,请你计算出有多少头绝对奶牛。

输入描述:

输入文件第一行是N和M。此后M行,每行两个整数A,B(1<=A,B<=N),表示奶牛B受奶牛A欢迎,也就是奶牛A喜欢奶牛B。

输出描述:

输出文件仅有一行,是绝对奶牛的数目。

输入样例:

3 3
1 2
2 1
2 3

输出样例:

1

数据范围:

对于30%的数据,有1<=N<=1000,1<=M<=5000;

对于100%的数据,有1<=N<=100000,1<=M<=500000。

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

这道题我初次想要用拓扑排序做,发现会超时

然后改成Tarjan... 请自行搜索Tarjan求强连通分支

后来发现大数据会RE

用-Wl,--stack=134217728(设定栈大小为128M)就好了

所以是暴递归栈了

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];
Edge* head[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;
        tmp->next = head[s];
        head[s] = tmp;
    }
    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++) {
        while(head[i] != NULL) {
            Edge* tmp = head[i]->next;
            delete head[i];
            head[i] = tmp;
        }
    }
    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;
        j = head[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;
        }
    }
}
时间: 01-19

总算把USACO的受欢迎奶牛做出来了的相关文章

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出发的射线!!! 然后你们还在玩概念!我跪了. (以上纯属蒟蒻吐槽) 好吧,计算几何非常有用的..简化了不少操作. 这里还有啥点积啥叉积.点积就是同一起点的向量(终点)的

[USACO] 2004 Open MooFest 奶牛集会

题目背景 MooFest, 2004 Open 题目描述 约翰的N 头奶牛每年都会参加"哞哞大会".哞哞大会是奶牛界的盛事.集会上的活动很 多,比如堆干草,跨栅栏,摸牛仔的屁股等等.它们参加活动时会聚在一起,第i 头奶牛的坐标为Xi,没有两头奶牛的坐标是相同的.奶牛们的叫声很大,第i 头和第j 头奶牛交流,会发出\(max{Vi, Vj}\) \(×\) \(|Xi ? Xj |\) 的音量,其中Vi 和Vj 分别是第i 头和第j 头奶牛的听力.假设每对奶牛之间同时都在说话,请计算所有

BZOJ 1706 usaco 2007 Nov relays 奶牛接力跑/POJ 3613 Cow Relays 倍增Floyd

题目大意:求恰好走k步从S到T的最短路. 思路:设f[p][i][j]为从i到j恰好走2^p步的最短路,DP方程十分简单:f[p][i][j] = min(f[p][i][j],f[p - 1][i][k] + f[p - 1][k][j]); 对总步数T进行二进制拆分,在T有1的位置上,假如这个位置为p,那么就用f[p][][]来更新答案g[][],最后得到的g[][]就是答案矩阵. 注意要离散化一下.. CODE: #include <cstdio> #include <cstrin

五款最受欢迎的编辑软件推荐

Notepad++ (Windows) Notepad++ 优于Windows记事本的一个文本编辑器,完全免费且开源,对于不同的编程语言可以实现语法高亮,代码折叠以及宏,起可定制性非常强. Emacs (所有平台) Emacs Emacs文本编辑器深受高级程序员的喜爱,具有内置的宏功能以及强大的键盘命令,这对于编辑代码来说真是一种享受,这个程序几乎被移植到了每一个平台,并有多个发行版,其中最流行的是GNU Emacs和XEmacs,它们是跨平台.完全免费并且开源. UltraEdit (Wind

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

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

7、8月刷题总结

准备开学了囧,7.8月刷题记录,以后好来复习,并且还要好好总结! 数据结构: splay: [BZOJ]1503: [NOI2004]郁闷的出纳员(Splay) [BZOJ]1269: [AHOI2006]文本编辑器editor(Splay) [BZOJ]1507: [NOI2003]Editor(Splay) treap: [BZOJ]1862: [Zjoi2006]GameZ游戏排名系统 & 1056: [HAOI2008]排名系统(treap+非常小心) [BZOJ]3224: Tyvj

oracle之sql查询二

此文章为http://huangsir007.blog.51cto.com/6159353/1854818该片的后续 关于数据库语言查询: SQL> show parameter nls_language; NAME                                 TYPE        VALUE ------------------------------------ ----------- ------------------------------ nls_languag

TYVJ P1029 牛棚回声 Label:坑

背景 USACO OCT09 3RD 描述 奶牛们灰常享受在牛栏中牟叫,因為她们可以听到她们牟声的回音.虽然有时候并不能完全听到完整的回音.Bessie曾经是一个出色的秘书,所以她精确地纪录了所有的牟叫声及其回声.她很好奇到底两个声音的重复部份有多长. 输入两个字符串(长度為1到80个字母),表示两个牟叫声.你要确定最长的重复部份的长度.两个字符串的重复部份指的是同时是一个字符串的前缀和另一个字符串的后缀的字符串. 我们通过一个例子来理解题目.考虑下面的两个牟声: moyooyoxyzooo