[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。

题目很好理解，解法就是按照压的关系连有向边，拓扑排序即可。亏我一开始还打了10分钟缩点。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn=1e6+;

int n,m,tot,ans;

int head[maxn],ru[maxn];

struct EDGE

{

    int to;int next;

}edge[maxn];

inline int read()

{

    char ch=getchar();

    int s=,f=;

    while (!(ch>=''&&ch<='')) {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

void add(int x,int y)

{

    edge[++tot]=(EDGE){y,head[x]};

    head[x]=tot;

}

void topo()

{

    queue <int> q;

    for (int i=;i<=n;i++) if (!ru[i]) {q.push(i);ans++;}

    while (!q.empty())

    {

        int k=q.front();q.pop();

        for (int i=head[k];i;i=edge[i].next)

        {

            int y=edge[i].to;

            ru[y]--;

            if (!ru[y])

            {

                ans++;

                q.push(y);

            }

        }

    }

}

int main()

{

    freopen("mikado.in","r",stdin);

    freopen("mikado.out","w",stdout);

    n=read();m=read();

    for (int i=;i<=m;i++)

    {

        int x=read(),y=read();

        add(x,y);

        ru[y]++;

    }

    topo();

    printf("%d\n",ans);

    return ;

}

竹签