The question :

Yes n Nodes ,m side , Undirected acyclic graphs , Find the minimum point cover , And under the same number of points, the maximum number of changes covered twice is guaranteed

analysis :

1. Unified goals , There are two objectives to be optimized , A minimum number of lights a, A maximum number of double covering edges b, One big one small , It should be one ,a And the number of single covering edges c,\( x=Ma+c \) To minimize the goal ,\( M>\Delta c \)

2. Decision analysis , There are only two kinds of lights and no lights , If you don't put the light on, you need the parent node to put the light on , So we need the state of the parent node , set up \( f(i,j) \) For the node i In the parent node, the state is j It's the smallest x value ,j by 0 It means no lights ,j by 1 On behalf of

\begin{cases}
    sum\{d(k,0)|k by i All child nodes \}+(i Root node ?0:1)&,i No lights \\
    sum\{d(k,1)|k by i All child nodes \}+M+(i Is not a root node and j==0?1:0)&,i\ Light up
    \end{cases}

The code is as follows

 /*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
int first[];
int Next[],U[];
bool vis[][];
int ans[][];
int cnt;
int M=<<;
void add(int u,int v) // Two way side
{
Next[cnt]=first[u]; first[u]=cnt; U[cnt++]=v;
Next[cnt]=first[v]; first[v]=cnt; U[cnt++]=u;
}
int dfs(int i,int j,int f)//i Is the current node ,j by 0 It means the parent node is not lit , by 1 It's for lights ,f by -1 Represents the root node
{
if(vis[i][j])return ans[i][j];
vis[i][j]=;
int k,&Ans=ans[i][j],ans0=;
Ans=;
for(k=first[i];~k;k=Next[k])
{
if(U[k]==f)continue;
Ans+=dfs(U[k],,i);// Light up
}
Ans+=M;
if(~f)
{
if(j)ans0++;
else Ans++;
}
if(j||f==-)
{
for(k=first[i];~k;k=Next[k])
{
if(U[k]==f)continue;
ans0+=dfs(U[k],,i); // No lights
}
Ans=min(Ans,ans0);
}
return Ans;
}
int main()
{
int T;
scanf("%d",&T);
int i,u,v;
while(T--)
{
cnt=;
memset(vis,,sizeof(vis));
memset(first,-,sizeof(first));
scanf("%d%d",&n,&m);
for(i=;i<m;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
}
int Ans=;
for(i=;i<n;i++)
{
if(!vis[i][])
Ans+=dfs(i,,-);
}
printf("%d %d %d\n",Ans>>,m-(Ans&(M-)),Ans&(M-));//Ans/M,m-Ans%M,Ans%M
}
}

uva 10859 - Placing Lampposts dp More articles about

  1. UVA 10859 - Placing Lampposts Tree form DP、 Take double best value

                              Placing Lampposts As a part of the mission ‘Beautification of Dhaka City’, ...

  2. UVA - 10859 Placing Lampposts Place street lights

    Placing Lampposts Portal :https://vjudge.net/problem/UVA-10859 The main idea of the topic : Here's a forest for you , Ask you to put lights on some nodes , A lighting lamp can illuminate all the connected ...

  3. UVa 10859 - Placing Lampposts Tree form DP difficulty : 2

    subject https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&a ...

  4. UVa 10859 Placing Lampposts

    This kind of deep recursion problem still needs a lot of experience , It's not enough just to see it once The question : There is a forest , Place a light at several nodes , The light can illuminate the edge adjacent to the node . requirement : What is the minimum number of lamps that meet the requirements , With the least number of lights , The number of sides on an edge illuminated by two lights at the same time ...

  5. UVA 10859 Placing Lamppost Tree form DP+ The solution of two objective optimal solution

    The question : Given an undirected , acyclic , No multiple edges , It is required to find out at least some points , bring , At least one point on each side has a street light . When the above conditions are satisfied, it is also necessary to make the number of edges selected as many as possible . Answer key : For how to find the minimum number of nodes ...

  6. UVaLive 10859 Placing Lampposts ( Tree form DP)

    The question : Given an undirected acyclic graph , Put lights on some of the vertices so that each side is illuminated , Ask the minimum number of lights , And illuminated by two lights on as many sides as possible . Analysis : It's actually a forest , Because it's independent , So we can look at each tree individually ,dp[i][0] Means not in ...

  7. 10_ Place street lights (Placing Lampposts,UVa 10859)

    Source of problem : Liu Rujia < Introduction to algorithm competition classic -- Training guide > P70 Example 30: Problem description : There's one for you n A little bit m side (m<n<=1000) The undirected acyclic graph of , Put lights on as few nodes as possible , So that all sides are illuminated ...

  8. UVa10895 Placing Lampposts

    UVa10895 Placing Lampposts link :http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34290 [ Ideas ] ...

  9. UVA.674 Coin Change (DP Completely backpack )

    UVA.674 Coin Change (DP) Problem analysis Yes 5 Grow coins , The denominations are 1.5.10.25.50, Now give the amount , How many ways can the denomination be made up . The number of each coin is unlimited . Typical complete backpack . state ...

Random recommendation

  1. Salesforce Learning materials

    Official document download website :https://developer.salesforce.com/docs About Salesforce All official documents of are in the above address , Preview and download online Recommend novices to learn the following documents ...

  2. [ translate ] understand PHP Definition of internal function ( to PHP Developer's PHP Source code - The second part )

    Article from :http://www.hoohack.me/2016/02/10/understanding-phps-internal-function-definitions-ch original text :https:/ ...

  3. [ original ]Spring MVC Study And - URL Parameter passing

    Original reference address : http://www.cnblogs.com/rhythmK/p/3971191.html Purpose and reason : I want to make a sharing page , Analyze and register with friends , Sign up and share ID Cascade ; The process : quite a lot ...

  4. EndNote Document management

    Always wanted to write a blog , But I haven't sat down to sort out my work . Let's start today , Try to write more . today , Let's first introduce a software that is often used in writing scientific papers EndNote, This software , It's very convenient to master how to use it : but ...

  5. Quick start software Rolan , You really can use ?

    2015.2.14 I'm very glad to Rolan This software is still being updated , And it's getting better ,UI The improvement in design and function of our company has shocked me a lot . Today, Rolan , You can compare 2014 Year map , It's really changed a lot : ...

  6. Flashback Version Query、Flashback Transaction Query Fast flashback of fine-grained data

    Flashback Version Query Flashback version query Use Flashback Version Query  Returns at a specified time interval or SCN All versions in the interval , once commit The command creates a version . ...

  7. Java Concurrent implementation of a ( The implementation of concurrency Thread and Runnable The difference between )

    package com.subject01; public class ThreadOrRunnable { public static void main(String[] args) { Syst ...

  8. jQuery Special effects Interlacing discoloration

    1. By using onmouseover onmouseout Method 2. Color change use background-color(css) attribute 3. The discolored label is td(tr You can only use events , Color styles don't work ) The first method Use ...

  9. java http post tomcat relieve Length limit

    1.    Get Method length limit Http Get There is no limit to the size and length of the data submitted by the ,HTTP The protocol specification is not correct URL Length restriction . This restriction is imposed by specific browsers and servers . Such as :IE Yes URL The length limit is 20 ...

  10. Android Use shape Make circular control and add bounce animation

    -------- Originally for the author , Reprint is prohibited without consent Preface : We need to be in a lot of times res/drawable Create the corresponding xml File to add some style effects to the control , For example, the button style changes when the button is pressed . Or specify the ...