树的路径覆盖

wjh15101051's space

卧薪尝胆，厚积薄发。

树的路径覆盖

Date: Tue Nov 06 15:24:42 CST 2018

In Category: NoCategory

Description：

给一棵树，求他的最小不相交点路径覆盖。

$1\leqslant n\leqslant 10^4,1\leqslant testcases\leqslant 10$

Solution：

不能算树形 $DP$ ，如果子树没有一个链可以连上来，那就给他新开一个，否则把一个子树的并上来，如果有多个，就合并两个，其他的截断。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 10010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int ans = 0;

bool v[MAXN];

int dfs(int k)

{

	v[k] = true;

	int sum = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		sum += dfs(e[i].to);

	}

	if(sum == 0)

	{

		++ans;

		return 1;

	}

	if(sum == 1)return 1;

	--ans;

	return 0;

}

void work()

{

	scanf("%d",&n);

	ans = 0;

	int a,b;

	memset(lin,0,sizeof(lin));

	edgenum = 0;

	memset(v,false,sizeof(v));

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	dfs(1);

	cout << ans << endl;

	return;

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}

In tag: DP-树形DP

wjh15101051