codeforces A. Sereja and Bottles 解题报告

题目链接：http://codeforces.com/problemset/problem/315/A

题目意思：有n个soda bottles，随后给出这n个soda bottles的信息。已知第 i 个bottle来自品牌ai，你可以用这个品牌 ai 来开所有属于品牌bi 的bottles。注意，other特别用黑色粗体来强调，表明该行的除外，也就是说，假如i = 1（隐含的），ai = 1，bi = 1，这个bottle 1 是不能被打开的。需要找出无论用什么方式都不能打开的bottle的总个数。

另外，有可能同一个bottle可以被多个不同的ai 打开，所以要增加一个额外的vis数组来防止已经打开的bottle不再重新被处理。

这条题目很久才读懂它的意思，真是要加强读题能力啊！！！

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 const int maxn =  + ;

 int a[maxn], b[maxn], vis[maxn];

 int main()

 {

     int i, j, n, cnt;

     while (scanf("%d", &n) != EOF)

     {

         for (i = ; i <= n; i++)

         {

             scanf("%d%d", &a[i], &b[i]);

         }

         memset(vis, , sizeof(vis));

         cnt = ;

         for (i = ; i <= n; i++)   // 从bottle 1开始搜索哪些a[j]可以打开它的

         {

             for (j = ; j <= n; j++)

             {

                 if (i != j && a[j] == b[i] && !vis[j])

                 {

                     cnt++;     // 记录能打开的bottle 数
         //            printf("a[%d] = %d\n", j, a[j]);

                     vis[j] = ;

                 }

             }

         }

         printf("%d\n", n - cnt);

     }

     return ;

 }

巴特西

codeforces A. Sereja and Bottles 解题报告

最新文章

热门文章