Description

Farmer John決定為他的所有奶牛都配備手機，以此鼓勵她們互相交流。不過，為此FJ必須在奶牛們居住的N(1 <=? N <= 10,000)塊草地中選一些建上無線電通訊塔，來保證任意兩塊草地間都存在手機信號。所有的N塊草地按1..N? 順次編號。 所有草地中只有N-1對是相鄰的，不過對任意兩塊草地A和B(1 <= A <= N; 1 <= B <= N; A != B)，都 可以找到一個以A開頭以B結尾的草地序列，并且序列中相鄰的編號所代表的草地相鄰。無線電通訊塔只能建在草地 上，一座塔的服務范圍為它所在的那塊草地，以及與那塊草地相鄰的所有草地。 請你幫FJ計算一下，為了建立能 覆蓋到所有草地的通信系統，他最少要建多少座無線電通訊塔。

Input

* 第1行: 1個整數，N * 第2..N行: 每行為2個用空格隔開的整數A、B，為兩塊相鄰草地的編號

Output

* 第1行: 輸出1個整數，即FJ最少建立無線電通訊塔的數目

Sample Input

5
1 3
5 2
4 3
3 5
輸入說明:
Farmer John的農場中有5塊草地：草地1和草地3相鄰，草地5和草地2、草地
4和草地3，草地3和草地5也是如此。更形象一些，草地間的位置關系大體如下：
（或是其他類似的形狀）
4 2
| |
1--3--5

Sample Output

2
輸出說明:
FJ可以選擇在草地2和草地3，或是草地3和草地5上建通訊塔。 思路：本題為動態規劃，dp[i][0]表示以i為根的子樹最少需要放幾個，同時i的父親沒有放。 dp[i][1]表示以i為根的子樹最少需要放幾個，同時i父親沒有放，但是已經被關聯。
dp[i][2]表示以i為根的字數最少需要放幾個，并且i的父親已經放了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define rep(i,a,b) for(R i=a;i<=b;i++) 5 #define Rep(i,a,b) for(R i=a;i>=b;i--) 6 #define rp(i,x) for(R i=H[x];i!=-1;i=E[i].nt) 7 #define ms(i,a) memset(a,i,sizeof(a)) 8 template<class T>void read(T &x){ 9 x=0; char c=0; 10 while (!isdigit(c)) c=getchar(); 11 while (isdigit(c)) x=x*10+(c^48),c=getchar(); 12 } 13 int const N=10000+3; 14 int const inf=1e8; 15 struct Edge{ 16 int to,nt; 17 }E[N<<1]; 18 int n,cnt,dp[N][3],H[N]; 19 void add(int a,int b){ 20 E[cnt]=(Edge){b,H[a]}; H[a]=cnt++; 21 } 22 void dfs(int x,int fa){ 23 int s1=0,s2=0; 24 rp(i,x){ 25 int v=E[i].to; 26 if(v==fa) continue; 27 dfs(v,x); 28 s1+=dp[v][1]; 29 s2+=dp[v][2]; 30 } 31 dp[x][0]=1+s2; 32 dp[x][1]=1+s2; 33 rp(i,x){ 34 int v=E[i].to; 35 if(v==fa) continue; 36 dp[x][1]=min(dp[x][1],s1-dp[v][1]+dp[v][0]); 37 } 38 dp[x][2]=min(1+s2,s1); 39 } 40 int main(){ 41 read(n); 42 ms(-1,H); 43 rep(i,1,n-1){ 44 int x,y; read(x);read(y); add(x,y); add(y,x); 45 } 46 dfs(1,1); 47 printf("%d\n",dp[1][1]); 48 return 0; 49 } View Code

?

轉載于:https://www.cnblogs.com/ZJXXCN/p/10208424.html

總結

以上是生活随笔為你收集整理的bzoj 1596 电话网络的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。