【POJ3659】【USACO 2008 Jan Gold】 3.Cell Phone Network 树上最小支配集/贪心 两种做法

题意:求树上最小支配集

最小支配集:点集,即每个点可以“支配”到相邻点,求最少点数可以使所有点被支配。

图上的最小支配集是NP的,但是树上的可以DP做,是O(n)的。


暴力做就好了,

f[i]表示此 点被选时的子树全支配的最小代价

g[i]表示其父亲节 点被选时的子树全支配的最小代价

h[i]表示其某子节 点被选时的子树全支配的最小代价


然后暴力转移。

(v是子节点)

f[x]=∑(min(f[v],min(g[v],h[v])))+1;
g[x]=∑(min(f[v],h[v]));  

h[x]: Ⅰ. 某个f[v]<=h[v]:h[x]=g[x]

      Ⅱ. 取个影响最小的f[v],即此v有f[v]-h[v]最小。其它v取min(f[v],h[v])此时即h[v]


呃,这个是正规做法,先附个代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 10100
#define inf 0x3f3f3f3f
using namespace std;
struct KSD
{
	int v,next;
}e[N<<1];
int head[N],cnt;
void add(int u,int v)
{
	cnt++;
	e[cnt].v=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
int n,f[N],g[N],h[N];
// 亮、父亮、子亮
void Tree_DP(int x,int p)
{
	int i,v,temp=20000;
	f[x]=1;
	bool flag=1,flag2=0;
	for(i=head[x];i;i=e[i].next)
	{
		v=e[i].v;
		if(v==p)continue;
		Tree_DP(v,x);
		f[x]+=min(f[v],min(g[v],h[v]));
		g[x]+=min(f[v],h[v]);
		temp=min(temp,f[v]-h[v]);
		if(f[v]<=h[v])flag2=1;
		flag=0;
	}
	if(flag)h[x]=inf;
	else {
		h[x]=g[x];
		if(!flag2)h[x]+=temp;
	}
	return ;
}
int main()
{
//	freopen("test.in","r",stdin);
	int i,j,k;
	int a,b,c;
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&a,&b);
		add(a,b),add(b,a);
	}
	Tree_DP(1,0);
	printf("%d\n",min(f[1],h[1]));
	return 0;
}


再附个很久以前写的贪心:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 10100
typedef struct KSD{int v,next;}ksd;ksd e[2*N];
int head[N],n,ans;
int attack[N],killed[N];
void add(int note,int u,int v){e[note].v=v;e[note].next=head[u];head[u]=note;}
void init()
{
	ans=0;
	memset(head,-1,sizeof(head));
	memset(attack,0,sizeof(attack));
	memset(killed,0,sizeof(killed));
}
void dfs(int x,int p)
{
	int i,j,k,t,v;
	for(t=head[x];t!=-1;t=e[t].next)
	{
		if(e[t].v!=p)
		dfs(e[t].v,x);
	}
	if(killed[x]==0)
	{
		ans++;
		attack[p]=killed[x]=killed[p]=1;
		for(t=head[p];t!=-1;t=e[t].next)
		{
			killed[e[t].v]=1;
		}
	}
}

int main()
{
//	freopen("test.in","r",stdin);
	int i,j,k;
	int a,b,c;
	while(scanf("%d",&n)!=EOF)
	{
		init();
		for(i=1;i<n;i++)
		{
			scanf("%d%d",&a,&b);
			add(i*2-1,a,b);
			add(i*2,b,a);
		}
		dfs(1,0);
		printf("%d\n",ans);
	}
	return 0;


郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。