NTPFECT - Đại diện hoàn hảo
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
const int N = 1111;
const int oo = 1234567;
using namespace std;
int par[N];
int n;
int f[N][2][2];
vector<int> a[N], child[N];
bool isLeaf[N];
void DFS(int u) {
if (a[u].size() == 1 && a[u][0] == par[u]) {
isLeaf[u] = true; return;
}
int i, v;
for(i=0; i<a[u].size(); i++) {
v = a[u][i];
if (v == par[u]) continue;
par[v] = u;
child[u].push_back(v);
DFS(v);
}
}
int DP(int u, int c, int p) {
if (f[u][c][p] >= 0) return f[u][c][p];
if (child[u].size() == 0) {
f[u][c][p] = c;
return f[u][c][p];
}
int i, v, s;
f[u][c][p] = oo;
if (c == 0) {
if (p == 0) {
s = 0;
for(i=0; i<child[u].size(); i++) {
v = child[u][i];
if (isLeaf[v]) s += DP(v, 1, 0);
else s += min(DP(v, 0, c), DP(v, 1, c));
}
for(i=0; i<child[u].size(); i++) {
v = child[u][i];
if (isLeaf[v]) continue;
f[u][c][p] = min(f[u][c][p], s + DP(v, 1, 0) - min(DP(v, 1, 0), DP(v, 0, 0)));
}
}
else {
f[u][c][p] = c;
for(i=0; i<child[u].size(); i++) {
v = child[u][i];
if (isLeaf[v]) f[u][c][p] += DP(v, 1, 0);
else f[u][c][p] += min(DP(v, 0, c), DP(v, 1, c));
}
}
}
else {
f[u][c][p] = c;
for(i=0; i<child[u].size(); i++) {
v = child[u][i];
f[u][c][p] += min(DP(v, 0, c), DP(v, 1, c));
}
}
return f[u][c][p];
}
int main()
{
int i, u, v, res;
while (true)
{
scanf("%d\n", &n);
if (n == 0) break;
for(i=1; i<=n; i++) {
a[i].clear(); par[i] = -1; child[i].clear(); isLeaf[i] = false;
f[i][0][0] = f[i][0][1] = f[i][1][0] = f[i][1][1] = -1;
}
res = n;
for(i=1; i<n; i++) {
scanf("%d %d\n", &u, &v);
a[u].push_back(v);
a[v].push_back(u);
}
DFS(1);
if (n > 1)
res = min(DP(1, 0, 0), DP(1, 1, 0));
printf("%d\n", res);
}
return 0;
}