Блог пользователя monyet

Автор monyet, 10 лет назад, По-английски

Hello, i'm trying to solve this problem http://www.spoj.com/problems/PT07X/. I wrote a brute force algorithm. I was expecting a Time Limit Exceeded response, but I got WA instead. What is wrong with my code? Thanks!

vector<pair<int,int> > edge;
     int n , a , b ,mini;
     
     scanf("%d",&n);
     for (int i = 1; i<=n-1; i++)
     {
         scanf("%d%d",&a,&b);
         a--; b--;
         edge.push_back(make_pair(a,b));
     }
     
     mini = INF;
     for (int mask = 0; mask < (1<<n); mask++)
     {
         bool can = true;
         for (int i = 0 ; i<edge.size(); i++)
         {
             if ( (mask&(1<<edge[i].first))==0 && (mask&(1<<edge[i].second))==0) 
             {
                  can = false;
                  break;
             }
         }
         
         if (can)
         {
             int on = 0;
             for (int i = 0 ; i<n; i++) if ( (mask&(1<<i))!= 0) on++;
             mini = min(mini,on);
         }
     }
     
     printf("%d\n",mini);
  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

for (int mask = 0; mask < (1<<n); mask++)

N<=100000

What do you expect?