posts - 74, comments - 33, trackbacks - 0

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1440		Accepted: 443

Description

Farmer John has decided to give each of his cows a cell phone in hopes to encourage their social interaction. This, however, requires him to set up cell phone towers on his N (1 ≤ N ≤ 10,000) pastures (conveniently numbered 1..N) so they can all communicate.

Exactly N-1 pairs of pastures are adjacent, and for any two pastures A and B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B) there is a sequence of adjacent pastures such that A is the first pasture in the sequence and B is the last. Farmer John can only place cell phone towers in the pastures, and each tower has enough range to provide service to the pasture it is on and all pastures adjacent to the pasture with the cell tower.

Help him determine the minimum number of towers he must install to provide cell phone service to each pasture.

Input

* Line 1: A single integer: N
* Lines 2..N: Each line specifies a pair of adjacent pastures with two space-separated integers: A and B

Output

* Line 1: A single integer indicating the minimum number of towers to install

Sample Input

Sample Output

Source

USACO 2008 January Gold
今天軟件工程的時候想通了這道題目成功的把3中狀態和DP聯系起來，以前思考的時候一直從root想leaves執行程序，而下午仔細想想如果從root出發，而執行程序的時候無法統計最后的點數，更可怕的是不是root影響leaves而是leaves影響著root的取值達到最優值！而這道題就是這樣可以計算下利用DFS遍歷Tree我們知道DFS時間度為O（n）空間上用鄰接表記錄關系圖,O(n)
說下3中狀態轉移，我就不講了，我這人口才不好，看寫的比說的清楚，哈哈~~
第一種狀態：就是一個節點不放置塔，而它的所有leaves被覆蓋，當然它自己能被它的leaves控制。
第二種狀態：一個節點和它的所有leaves全被覆蓋，而這個節點放置控制塔。
第三種狀態：一個節點暫時沒有被覆蓋，也沒有放置節點。
DFS函數如下：

void?DFS(int?x){

????int?i,sign,flag;

????for(flag=sign=i=0;i<v[x].size();i++){

????????int?t=v[x][i];

???????????if(!mark[t]){

????????????sign=1;mark[t]=1;

????????????DFS(v[x][i]);

????????????if(dp[t][0]<dp[t][1])dp[x][0]+=dp[t][0];

?????????????else?{

??????????????????dp[x][0]+=dp[t][1];

??????????????????sign=1;

?????????????}

?????????????dp[x][1]+=getmin(getmin(dp[t][0],dp[t][1]),dp[t][2]);

?????????????dp[x][2]+=dp[t][0];

???????????}

????}

????if(!sign)dp[x][0]=dp[x][1]=1;

????else{

????????dp[x][1]++;

???????????if(!flag)dp[x][0]+=1;

????}

}

posted on 2009-04-09 21:45 KNIGHT 閱讀(318) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

2009年4月

日

一

二

三

四

五

六

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

2009年3月 (1)

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

Friends

OJ

搜索

最新評論

閱讀排行榜

評論排行榜