[训练指南] 树形DP 多目标最优化 有优先级的优化量 UVa10859

题意给出森林,让在放置的点数尽量少的情况下保证每条边都被点覆盖到(乍一看二分图匹配?),然后在此前提下再要求被两个点同时覆盖到的边最多。两个需要解决的的:1 怎么把这个多目标最优化解决了 2  怎么处理不同节点之间的影响

第一个问题书上的解决办法是用一个新的变量x=aM+c代替对M和对c求最小的操作,M是比c的可能取值范围还要大的常数。这样的话,比较的时候就是先比较a再比较c了。

第二个问题,首先可以试着直接用dp(x)代表以节点x为根的子树的x最小值,但是这样会发现存在问题,因为一层放不放灯是和他的相邻节点有关系的,如果相邻节点都不放那他只能放了。所以再加入一个其他节点对他的影响。由于我们的dp方向是从树根向下(这样比较简单),所以我们选择保存父节点的放灯与否的状态,这时候状态为dp(i,j),其中j为0/1表示父节点 不放/放。这样就可以分放与不放来考虑了,然后求一个min即可。

实现的话就边dfs边dp就好了,用一个数组p[x]来存储父节点

/*

*/
//#include
#include 
#include 
#include 
#include
#include
#include
#include
#include
#include
//#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=1e3+5;
const int MA=2000;
const int MOD=1e9+7;

vectorG[1005];

int vis[1005][2],d[1005][2],p[1005];

int dfs(int i,int j)
{
    //cout<

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据