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;
}