首页 > ACM题库 > UVA > Uva-10859-Placing Lampposts-树形dp[解题报告]
2014
02-18

Uva-10859-Placing Lampposts-树形dp[解题报告]

Placing Lampposts

As a part of the mission �Beautification of Dhaka City�, the government has decided to replace all the old lampposts with new expensive ones. Since the new ones are quite expensive and the budget is not up to the requirement, the government has decided to buy the minimum number of lampposts required to light the whole city.

Dhaka city can be modeled as an undirected graph with no cycles, multi-edges or loops. There are several roads and junctions. A lamppost can only be placed on junctions. These lampposts can emit light in all the directions, and that means a lamppost that is placed in a junction will light all the roads leading away from it.

The �Dhaka City Corporation� has given you the road map of Dhaka city. You are hired to find the minimum number of lampposts that will be required to light the whole city. These lampposts can then be placed on the required junctions to provide the service. There could be many combinations of placing these lampposts that will cover all the roads. In that case, you have to place them in such a way that the number of roads receiving light from two lampposts is maximized.

Input

There will be several cases in the input file. The first line of input will contain an integer T(T<=30) that will determine the number of test cases. Each case will start with two integers N(N<=1000) and M( M<N) that will indicate the number of junctions and roads respectively. The junctions are numbered from 0 to N-1. Each of the next M lines will contain two integers a and b, which implies there is a road from junction a to b,
( 0<= a,b < N ) and a != b. There is a blank line separating two consecutive input sets.

Output

For each line of input, there will be one line of output. Each output line will contain 3 integers, with one space separating two consecutive numbers. The first of these integers will indicate the minimum number of lampposts required to light the whole city. The second integer will be the number of roads that are receiving lights from two lampposts and the third integer will be the number of roads that are receiving light from only one lamppost.

Sample Input

2
4 3
0 1
1 2
2 35 4
0 1
0 2
0 3
0 4

Sample Output

2 1 2
1 0 4

题目大意:给定一个无向无环图,要求在点上放灯,如果某一点上放了等,则可以照亮与它相通的边,现在要求放尽量少得等,使得所有边都被照亮,并且输出灯数,被照亮两次的边数(即边的两个端点均放置灯),被照亮一次的边。 如果等数一样的话,按照被照亮一次边越大的方案。

解题思路:树形dp,每次枚举某个顶点作为根,对于每个点有放与不放两种可能,均进行考虑;然后每放一盏灯+2000(因为边的最大数量为1000),每增加1条照亮一次的边+1.

#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
const double eps(1e-8);
typedef long long lint;
#define clr(x) memset( x , 0 , sizeof(x) )
#define repf(i, a, b) for (int i = (a); i <= (b); ++i)
#define repd(i, a, b) for (int i = (a); i >= (b); --i)
#define clrs( x , y ) memset( x , y , sizeof(x) )
vector<int>adj[1010];
int d[1010][2],n,m;
int dp(int i,int j,int f)
{
    if(d[i][j]>=0)return d[i][j];
    int &ans=d[i][j];
    ans=2000;
    for(int k=0;k<adj[i].size();k++)
    {
        if(adj[i][k]!=f)
            ans+=dp(adj[i][k],1,i);
    }
    if(j==1||f==-1)
    {
       int sum=0;
       for(int k=0;k<adj[i].size();k++)
       {
         if(adj[i][k]!=f)
         {
             sum+=dp(adj[i][k],0,i);
             sum++;
         }
       }
       if(f>=0)sum++;
       ans=min(ans,sum);
    }
    return ans;
}
int main()
{
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
       scanf("%d%d",&n,&m);
       for(int i=0;i<n;i++)adj[i].clear();
       for(int i=0;i<m;i++)
       {
           int t1,t2;
           scanf("%d %d",&t1,&t2);
           adj[t1].push_back(t2);
           adj[t2].push_back(t1);
       }
       memset(d,-1,sizeof(d));
       int ans=0;
       for(int i=0;i<n;i++)
           if(d[i][1]==-1)ans+=dp(i,0,-1);
       printf("%d %d %d\n",ans/2000,m-ans%2000,ans%2000);
    }
    return 0;
}

  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks