UVA10859 Placing Lampposts

我是题面

这道题使我知道了一种很神奇的方法，一定要认真看哦

如果没有被两盏灯同时照亮的边数应尽量大这个限制的话，这就是一道很经典的树形DP题——没有上司的舞会

很可惜，这个限制就在那里，它使得我辛苦写出来的贪心是错的，我只能做到尽量小 /托腮

由于总的边数是确定的，我们可以通过维护被一盏灯照亮的边最小来维护题目限制

我们考虑一下没有这个条件的话，DP该怎么写

用$f[i][0/1]$表示是否点亮第$i$盏灯时最少点亮几盏灯

我们考虑怎么把边数加进去一起维护呢？

再加一维的话就是$f[i][j][0/1]$，表示是否点亮第$i$盏灯点亮了$j$盏灯最少有多少条边被一盏灯照亮

应该能过，但是我不是这么写的，我有一种更优美的写法

我们用$f[i][0/1]$来维护是否点亮第$i$盏灯时，最少点亮了几盏灯以及最少有多少条边被一盏灯照亮

问题来了，一个数怎么维护两个信息呢？

相信很多人已经差不多想出来了，我们可以用一个$K$进制数来表示啊

$f[i][0/1]/K$表示最少点亮了几盏灯，$f[i][0/1]%K$表示最少有多少条边被一盏灯照亮

同时维护两个值，是不是很优美，至于K的取值只要比$m$大即可，这里我们可以取1000

转移时

$f[u][0]= \sum (f[v][1]+1) $，$u$节点不点亮的话，就是每条边都是点亮一次

$f[u][1]=( \sum min(f[v][1],f[u][0]+1))+K$，$u$节点点亮的话，$v$节点没有点亮的边点亮一次

下面就直接看代码吧

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cctype>

#define ll long long

#define gc getchar

#define maxn 1005

#define K 1000

using namespace std;

inline ll read(){

	ll a=0;int f=0;char p=gc();

	while(!isdigit(p)){f|=p=='-';p=gc();}

	while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}

	return f?-a:a;

}int t,n,m,ans;

struct ahaha{

	int to,next;

}e[maxn<<1];int tot,head[maxn];

inline void add(int u,int v){

	e[tot]={v,head[u]};head[u]=tot++;

}

int f[maxn][2];

void dfs(int u,int fa){f[u][1]=K;

	for(int i=head[u];~i;i=e[i].next){

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

		dfs(v,u);f[u][0]+=f[v][1]+1;

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

	}

}

inline void clear(){ans=tot=0;

	memset(f,0,sizeof f);

	memset(head,-1,sizeof head);

}

int main(){

	t=read();

	while(t--){clear();

		n=read();m=read();

		for(int i=1;i<=m;++i){

			int u=read()+1,v=read()+1;

			add(u,v);add(v,u);

		}

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

			if(!f[i][1]){

				dfs(i,-1);

				ans+=min(f[i][0],f[i][1]);

			}

		printf("%d %d %d\n",ans/K,m-ans%K,ans%K);

	}

	return 0;

}

不要抄代码哦

巴特西

UVA10859 Placing Lampposts

最新文章

热门文章