POJ1848 Tree 【树形dp】

题目链接

题解

由题，一个环至少由三个点组成，一个点作为根时，可以单独成链，可以与其一个儿子成链，或者与其两个儿子成环，与其一个剩余链长度大于等于2的儿子成环。

那么我们设最小代价

\(f[u][0]\)表示以\(u\)为根全部成环

\(f[u][1]\)表示除\(u\)外全部成环

\(f[u][2]\)表示除\(u\)和一个儿子的一条长度至少为\(1\)的链外全部成环

转移就很容易想

记\(sum = \sum\limits_{(u,v) \in edge} f[v][0]\)

\[f[u][1] = sum
\]

\[f[u][2] = min\{\sum\limits_{(u,v) \in edge} min(f[v][1],f[v][2]) + (sum - f[v][0]) \}
\]

\[f[u][0] = min\{ \sum\limits_{(u,v) \in edge} \sum\limits_{(u,k) \in edge} min(f[v][1],f[v][2]) + min(f[k][1],f[k][2]) + (sum - f[v][0] - f[k][0]) + 1\}
\]

\[f[u][0] = min\{ \sum\limits_{(u,v) \in edge} f[v][2] + (sum - f[v][0]) + 1 \}
\]

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define LL long long int

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");

using namespace std;

const int maxn = 105,maxm = 100005,INF = 1000000000;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

int h[maxn],ne = 2;

struct EDGE{int to,nxt;}ed[maxn << 1];

inline void build(int u,int v){

	ed[ne] = (EDGE){v,h[u]}; h[u] = ne++;

	ed[ne] = (EDGE){u,h[v]}; h[v] = ne++;

}

int n,fa[maxn],s[maxn];

LL f[maxn][3];

void dfs(int u){

	f[u][0] = f[u][2] = INF; f[u][1] = 0; LL sum = 0;

	Redge(u) if ((to = ed[k].to) != fa[u]){

		fa[to] = u; dfs(to);

		f[u][1] += f[to][0];

		sum += f[to][0];

	}

	int cnt = 0; LL tmp;

	Redge(u) if ((to = ed[k].to) != fa[u]){

		s[++cnt] = to;

		f[u][2] = min(f[u][2],min(f[to][1],f[to][2]) + sum - f[to][0]);

		f[u][0] = min(f[u][0],f[to][2] + sum - f[to][0] + 1);

	}

	REP(i,cnt) REP(j,cnt) if (i != j){

		tmp = min(f[s[i]][1],f[s[i]][2]) + min(f[s[j]][1],f[s[j]][2]) + sum - f[s[i]][0] - f[s[j]][0];

		f[u][0] = min(f[u][0],tmp + 1);

	}

}

int main(){

	while (~scanf("%d",&n) && n){

		ne = 2; memset(h,0,sizeof(h));

		for (int i = 1; i < n; i++) build(read(),read());

		dfs(1);

		if (f[1][0] >= INF) puts("-1");

		else printf("%lld\n",f[1][0]);

	}

	return 0;

}

巴特西

POJ1848 Tree 【树形dp】

题目链接

题解

最新文章

热门文章