UVa10895 Placing Lampposts
链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34290
【思路】
树上DP+双重优化目标。
本题的特点就是有两个优化目标分别为：在尽量少的结点放灯、在此前提下有被两盏灯照亮的边最多。
首先进行转化：将第二个优化目标转化为在此前提下被一盏灯照亮的边最少。这样两个优化目标就都是求最小值。用一个hash(A,B)将两个新的优化目标AB映射到一个整数，转化为求这个整数的最小值，可以定义hash=A*M+B完成这个功能，M是一个较大数。
树上DP。设d[i][j]表示以i为根的子树且有父节点状态为j时的最优值，注意用j记录父节点状态。有如下转移式：
略。详见代码。
【代码】
#include<iostream>
#include<cstring>
#include<vector>
using namespace std; const int maxn = +;
const int INF=<<;
const int M=; vector<int> G[maxn];
int d[maxn][];
bool vis[maxn][];
int n,m; inline void init() {
for(int i=;i<n;i++) G[i].clear();
memset(vis,false,sizeof(vis));
memset(d,,sizeof(d));
} int dp(int i,int j,int fa) {
if(vis[i][j]) return d[i][j];
vis[i][j]=true;
int &ans=d[i][j]; //无论j都可以在i上放置街灯
ans=M; //放置一个街灯的价值
for(int k=;k<G[i].size();k++) {
int v=G[i][k];
if(v!=fa) {
ans += dp(v,,i);
}
}
if(!j && fa>=) ans++; // if(j || fa<) //根也可以不放
{
int sum=;
for(int k=;k<G[i].size();k++) {
int v=G[i][k];
if(v!=fa) {
sum += dp(v,,i);
}
}
if(fa>=) sum++; //10 //根不算
ans=min(ans,sum); //两种情况取min
} return ans;
} int main() {
ios::sync_with_stdio(false);
int T; cin>>T;
while(T--)
{
cin>>n>>m;
init();
int u,v;
for(int i=;i<m;i++) {
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
int ans=;
for(int i=;i<n;i++) if(!vis[i][]) {
ans += dp(i,,-);
}
cout<<ans/M<<" "<<m-ans%M<<" "<<ans%M<<"\n";
}
return ;
}