NTPFECT - Đại diện hoàn hảo
Tác giả: flashmt
Ngôn ngữ: C++
#include<iostream>
#include<algorithm>
#define fr(a,b,c) for (a=b;a<=c;a++)
#define frr(a,b,c) for (a=b;a>=c;a--)
using namespace std;
int n,p[1111],a[2222],b[1111],c[1111],f[1111],g[1111];
void visit(int x,int y)
{
int i,t=10000,u=0,v=0;
if (p[x]+1==p[x+1] && y) return;
fr(i,p[x]+1,p[x+1])
if (a[i]!=y)
{
visit(a[i],x);
t=min(t,f[a[i]]-g[a[i]]);
u+=g[a[i]];
}
g[x]=min(f[x],u+t);
f[y]+=min(g[x],u);
}
int main()
{
//freopen("pfect.in","r",stdin); freopen("pfect.out","w",stdout);
int i,j;
while (1)
{
cin >> n;
if (!n) break;
fr(i,1,n+1)
{
p[i]=0; f[i]=1; g[i]=1;
}
fr(i,1,n-1)
{
scanf("%d%d",&b[i],&c[i]);
p[b[i]]++; p[c[i]]++;
}
fr(i,2,n+1) p[i]+=p[i-1];
fr(i,1,n-1)
{
a[p[b[i]]--]=c[i];
a[p[c[i]]--]=b[i];
}
visit(1,0);
cout << g[1] << endl;
}
//fclose(stdin); fclose(stdout);
return 0;
}