UVA 10859 Placing Lampposts (动态规划)

题意：一个n个点m条边的无向无环图，在尽量少的节点上放灯，使得所有边都被照亮，每盏灯将照亮以它为一个端点的所有边，在总灯数最小的前提下，被两盏灯同时照亮的边数应尽量大。

思路：无向无环图就是“森林”，常用树形dp，本题要优化的目标有两个，放置的灯数a应尽量少，被两盏灯同时照亮的边数b应尽量大，为了统一，我们把b替换成”恰好被一盏灯照亮的边数c尽量小“。然后设x=Ma+c为最终的优化目标，M是一个很大的正整数。当x取最小值的时候，x/M就是a的最小值，x%M就是c最小值。

定义dp(i,j)，其中i表示节点i，j表示节点i的父节点是否放置了街灯，0代表没放，1代表放了，则dp(i,j)代表在上述下x的最小值。

实际上，对于每个节点而言，只有两种决策：在i处放或者不放街灯。

决策一：节点i处不放街灯，那么i是根或者父亲节点放了街灯。所以dp(i,j)=sum{ dp(v,0) | v取遍i的所有儿子节点 }，如果i不是根节点，那么结果+1，因为i和父亲连接的这条边只被一盏灯照亮。

决策二：节点i处放街灯，dp(i,j)=sum{ dp(v,1)| v取遍i的所有儿子节点 } + M，如果i不是根节点而且j=0，那么结果+1。

总结：以后遇到需要同时优化两个量v1,v2的问题，要求首先满足v1最小，在这个前提下v2最小的问题，可以考虑优化x=M*v1+v2，其中M是比"比v2的最大理论值和v2的最小理论值之差"还要大的数。


 #include<iostream>   
#include<cstdio>   
#include<cstring>   
#include<cmath>   
#include<algorithm>   
#include<string>   
#include<vector>   
#include<queue>   
#include<stack>   
#define INF 0x3f3f3f3f   
#define NODENUM 1005   
#define EDGENUM 1005   
#define MAXN 1005   
using namespace std;  
  
int root;  
const int m=2000;  
  
struct EdgeNode{int to,next;} E[2*EDGENUM];  
int edgenum,head[NODENUM],N,T,M;  
bool vis[NODENUM];  
int ans,dp[NODENUM][2];  
  
void init()  
{  
    edgenum=0;  
    memset(head,-1,sizeof(head));  
    memset(vis,0,sizeof(vis));  
    ans=0;  
}  
  
void add(int x,int y)  
{  
    edgenum++;  
    E[edgenum].next=head[x];  
    head[x]=edgenum;  
    E[edgenum].to=y;  
}  
  
void dfs(int s)  
{  
    vis[s]=1;  
    int sum0=0,sum1=0;  
      
    for(int p=head[s];p!=-1;p=E[p].next)  
    {  
        int v=E[p].to;  
        if(!vis[v])   
        {  
            dfs(v);  
            sum0+=dp[v][0];  
            sum1+=dp[v][1];  
        }  
    }  
  
    if(s==root) dp[s][0]=min(sum1+m,sum0),ans+=dp[s][0];  
    else dp[s][1]=min(sum0+1,sum1+m),dp[s][0]=sum1+m+1;  
      
}  
  
void build()  
{  
    scanf("%d%d",&N,&M);  
    for(int i=0;i<M;++i)  
    {  
        int a,b;  
        scanf("%d%d",&a,&b);  
        add(a,b);  
        add(b,a);  
    }  
}  
  
int main()  
{  
    scanf("%d",&T);  
    while(T--)  
    {  
        init();  
        build();  
        for(int i=0;i<N;++i) if(!vis[i]) dfs(root=i);  
        printf("%d %d %d\n",ans/m,M-ans%m,ans%m);  
    }  
    return 0;  
}  

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#define INF 0x3f3f3f3f
#define NODENUM 1005
#define EDGENUM 1005
#define MAXN 1005
using namespace std;

int root;
const int m=2000;

struct EdgeNode{int to,next;} E[2*EDGENUM];
int edgenum,head[NODENUM],N,T,M;
bool vis[NODENUM];
int ans,dp[NODENUM][2];

void init()
{
	edgenum=0;
	memset(head,-1,sizeof(head));
	memset(vis,0,sizeof(vis));
	ans=0;
}

void add(int x,int y)
{
	edgenum++;
	E[edgenum].next=head[x];
	head[x]=edgenum;
	E[edgenum].to=y;
}

void dfs(int s)
{
	vis[s]=1;
	int sum0=0,sum1=0;
	
	for(int p=head[s];p!=-1;p=E[p].next)
	{
		int v=E[p].to;
		if(!vis[v]) 
		{
			dfs(v);
			sum0+=dp[v][0];
			sum1+=dp[v][1];
		}
	}

	if(s==root) dp[s][0]=min(sum1+m,sum0),ans+=dp[s][0];
	else dp[s][1]=min(sum0+1,sum1+m),dp[s][0]=sum1+m+1;
	
}

void build()
{
	scanf("%d%d",&N,&M);
	for(int i=0;i<M;++i)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		init();
		build();
		for(int i=0;i<N;++i) if(!vis[i]) dfs(root=i);
		printf("%d %d %d\n",ans/m,M-ans%m,ans%m);
	}
	return 0;
}

补充：软件开发 , C++ ,