BZOJ2369【Tree DP】
/* I will wait for you */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <string>
#define make make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int maxn = 100010;
const int maxm = 1010;
const int maxs = 26;
const int inf = 0x3f3f3f3f;
const int P = 1000000007;
const double error = 1e-9;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
f = (ch == '-' ? -1 : 1), ch = getchar();
while (ch >= '0' && ch <= '9')
x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
struct edge
{
int v, next;
} e[maxn];
int n, cnt, f[maxn][20], head[maxn];
void insert(int u, int v)
{
e[cnt] = (edge) {v, head[u]};
head[u] = cnt++;
e[cnt] = (edge) {u, head[v]};
head[v] = cnt++;
}
void dfs(int u, int p)
{
for (int i = 1; i <= 10; i++)
f[u][i] = i;
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (v != p) {
dfs(v, u);
for (int j = 1; j <= 10; j++) {
int val = inf;
for (int k = 1; k <= 10; k++)
if (j != k)
val = min(val, f[v][k]);
f[u][j] += val;
}
}
}
}
int main()
{
n = read();
memset(head, -1, sizeof head);
for (int i = 1; i < n; i++) {
int u = read(), v = read();
insert(u, v);
}
dfs(1, 0);
int ans = inf;
for (int i = 1; i <= 10; i++)
ans = min(ans, f[1][i]);
printf("%d
", ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.