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);
for (int mask = 0; mask < (1<<n); mask++)
N<=100000
What do you expect?
an overflow >.< thanks dude