JZOJ 4269. 【NOIP2015模拟10.27】挑竹签

traveller-ly 2018-07-19 原文

JZOJ 4269. 【NOIP2015模拟10.27】挑竹签

Description

挑竹签——小时候的游戏
夏夜，早苗和诹访子在月光下玩起了挑竹签这一经典的游戏。
挑竹签，就是在桌上摆上一把竹签，每次从最上层挑走一根竹签。如果动了其他的竹签，就要换对手来挑。在所有的竹签都被挑走之后，谁挑走的竹签总数多，谁就胜了。
身为神明的诹访子自然会让早苗先手。为了获胜，早苗现在的问题是，在诹访子出手之前最多能挑走多少竹签呢？
为了简化问题，我们假设当且仅当挑最上层的竹签不会动到其他竹签。

Input

输入文件mikado.in。
第一行输入两个整数n,m, 表示竹签的根数和竹签之间相压关系数。
第二行到m+1 行每行两个整数u,v，表示第u 根竹签压住了第v 根竹签。

Output

输出文件mikado.out。
一共一行，一个整数sum，表示最多能拿走sum 根竹签。

Sample Input

Sample Output

3
样例解释：
一共有6 根竹签，其中1 压住2，2 压住3，3 压住1，4 压住3 和5，6 压住5。最优方案中，我们可以依次挑走4、6、5 三根竹签。而剩下的三根相互压住，都无法挑走。所以最多能挑走3 根竹签。

Data Constraint

对于20% 的数据，有1<= n,m<= 20。
对于40% 的数据，有1 <= n,m <= 1 000。
对于100% 的数据，有1 <= n,m <= 1 000 000。

做法：不难发现，对于a 压住 b 这种情况，可以由 a 向 b 连一条边，然后拓扑排序找最长链就好了。

代码如下：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <string>
 5 #define N 1000007
 6 using namespace std;
 7 struct edge
 8 {
 9     int to, next;
10 }e[N * 2];
11 int rd[N], n, m, ls[N], tot, list[N];
12 bool v[N];
13 
14 int read()
15 {
16     int s = 0;
17     char c = getchar();
18     while (c < '0' || c > '9')    c = getchar();
19     while (c >= '0'    && c <= '9')    s = s * 10 + c - '0', c = getchar();
20     return s;
21 }
22 
23 int main()
24 {
25     freopen("mikado.in", "r", stdin);
26     freopen("mikado.out", "w", stdout);
27     n = read(), m = read();
28     for (int i = 1; i <= m; i++)
29     {
30         int x, y;
31         x = read(), y = read();
32         rd[y]++;
33         e[++tot].to = y;
34         e[tot].next = ls[x];
35         ls[x] = tot;
36     }
37     int head = 0, tail = 0;
38     for (int i = 1; i <= n; i++)
39         if (rd[i] == 0)    list[++tail] = i, v[i] = 1;
40     while (head <= tail)
41     {
42         head++;
43         for (int i = ls[list[head]]; i; i = e[i].next)
44         {
45             rd[e[i].to]--;
46             if (rd[e[i].to] == 0 && !v[e[i].to])
47             {
48                 v[e[i].to] = 1;
49                 list[++tail] = e[i].to;    
50             }    
51         }    
52     }
53     printf("%d", tail);
54 }