【日常学习】【树形DP】【树的最小点覆盖】tyvj1377 荒山突围题解

左手的ㄟ右手 2022-08-09 14:41 140阅读 0赞

**P1377** 荒山突围

时间: 1000ms / 空间: 131072KiB / Java类名: Main

## 描述 ##

自从小A通过你的帮助逃出死亡城堡之后，死亡城堡的堡主发出了“死亡通缉令”，命令其手下的死亡精灵通缉小A。为了保住小A的RP，下面交给你了。  
在这座荒山之上，原先存在着n个传送屋，并且这些传送屋都是通过时空洞连在一起的，小A可以从任何一个小屋到达另外的一个小屋（计穿梭一次），并且当小A穿梭一次需要耗费的体力为1。但是，光这样穿梭也不行啊？外面道路上可是充满了死亡精灵。现在，小A需要消灭掉这座荒山所有道路上的死亡精灵才能顺利的逃脱死亡城堡堡主的围捕。已知在这些传送屋与传送屋之间可能有很多的道路，在每一条道路上都会存在一些死亡精灵。并且对于每一个小屋来说，都存在一个原能发射器，你可以通过这些传送屋之间的时空洞在各个传送屋之间穿梭去引发原能发射器。每当一个小屋的原能发射器被引发之后，所有与该小屋相连的道路上的死亡精灵都会被你的原能之光化解掉。（不要妄想小A直接去道路上和敌人PK，那可是死亡精灵！）  
现在，你的起始点可以在任意的一个小屋内，并且可以引发该小屋内的原能发射器。请你编写一个程序，使小A能够耗费最少的体力而消灭掉该荒山上的所有死亡精灵。你的程序仅需输出小A在消灭掉最后一批死亡精灵之后耗费的最小体力值。

## 输入格式 ##

第1行：n，表示传送屋的数量。  
以下n行：第i+1行描述传送屋i(1..n)的信息。一共有多个整数，表示与该传送屋i之间存在道路的传送屋的编号，每两个整数之间有一个空格，最后一个0代表着行的结束。  
在输入文件中保证两点之间最多存在一条直接或间接的道路,保证不会爆栈（什么意思？自己理解吧）。

## 输出格式 ##

输出文件仅包含一个数，为小A在消灭掉最后一批死亡精灵之后耗费的最小体力值。

## 测试样例1 ##

### 输入 ###

> 样例一：   
> 5   
> 2 0   
> 1 3 0   
> 2 4 0   
> 3 5 0   
> 4 0   
> 样例二：   
> 6   
> 2 5 0   
> 1 0   
> 4 0   
> 3 6 5 0   
> 4 1 0   
> 4 0

### 输出 ###

> 样例一：   
> 1   
> 样例二：   
> 1

## 备注 ##

对于30%的数据：1<=n<=500  
对于100%的数据：1<=n<=500,000

这道题目原本毫无思路，多亏里奥神犇讲解~

实际上是求树的最小点覆盖问题  
树的最小点覆盖问题，就是求最少多少个点，他们连接的边能够覆盖这棵树的所有边  
  
  
我们用f\[i\]\[0\]表示对于不选当前节点时其子树的最小点覆盖，f\[i\]\[1\]表示选这个点时的情况  
如果不选，由于要覆盖这个点和他儿子相连的边，因此这个店的所有儿子必须全部选上，即转移方程为f\[i\]\[0\]=sum(f\[j\]\[0\]),fa\[j\]=i  
如果选上，那么这个点的儿子节点就可选可不选了，因此f\[i\]\[1\]=sum(min(f\[j\]\[0\],f\[j\]\[1\])),fa\[j\]=i  
  
  
最后我们只要把所有根节点两种状态取最小值相加即可。对于这道题目，由于刚开始可以任选一个点，我们不妨让他恰好为最小覆盖中的某个点，这样可以节省一点能量，因此将方才求得的总和减一即可

代码

//tyvj1377 荒山突围 树的最小点覆盖-树形DP
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int maxn=500000+10;
    
    int hd[maxn],t[maxn*2],nxt[maxn*2],et=0;
    bool vis[maxn];
    int n,ans=0;
    int f[maxn][2];//0 not choose
    
    inline int read()
    {
    	int a=0;
    	char ch=getchar();
    	while (ch<'0'||ch>'9')
    	{
    		ch=getchar();
    	}
    	while (ch>='0'&&ch<='9')
    	{
    		a=a*10+ch-'0';
    		ch=getchar();
    	}
    	return a;
    }
    
    void add(int u,int v)
    {
    	et++;
    	t[et]=v;
    	nxt[et]=hd[u];
    	hd[u]=et;
    }
    
    void dfs(int i)
    {
    	for (int j=hd[i];j;j=nxt[j])
    	{
    		int tt=t[j];
    		if (!vis[tt])
    		{
    			vis[tt]=true;
    			dfs(tt);
    			f[i][0]+=f[tt][1];
    		    f[i][1]+=min(f[tt][1],f[tt][0]);
    		}
    	}
    	f[i][1]++;
    }
    
    int main()
    {
    	freopen("1.txt","r",stdin);
    	freopen("2.txt","w",stdout);
    	n=read();
    	int x;
    	memset(hd,0,sizeof(hd));
    	memset(f,0,sizeof(f));
    	for (int i=1;i<=n;i++)
    	{
    		while (x=read())
    		{
    			add(i,x);
    		}
    	}
    	memset(vis,false,sizeof(vis));
    	for (int i=1;i<=n;i++) if (!vis[i])
    	{
    		vis[i]=true;
    		dfs(i);
    		ans+=min(f[i][0],f[i][1]);
    	}
    	printf("%d\n",ans-1);
    	return 0;
    }

古诗文要和上一次成双成对

——徘徊庭树下，自挂东南枝