POJ 3659 Cell Phone Network（树的最小支配集）（贪心）-白红宇

POJ 3659 Cell Phone Network（树的最小支配集）（贪心）

阅读量：7092 次

发布时间：2019-06-28

本文共 2090 字，大约阅读时间需要 6 分钟。

Cell Phone Network

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 6781		Accepted: 2429

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

51 35 24 33 5

Sample Output

Source

【分析】给你一棵树，当你给一个节点染色时，他的相邻节点都会被染上色，问最少选择多少节点染色，可以将整棵树染上。

这是树的最小支配集模板题，贪心做的。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #define inf 10000000#define mod 10000typedef long long ll;using namespace std;const int N=2e4+10;const int M=50000;int in[N],vis[N];int n,m,k,tim=0;int newpos[N],p[N];vector
                   
                    vec[N],edg[N];bool s[N],se[N];void dfs(int u,int fa){ newpos[tim++]=u; // printf("%d %d\n",tim-1,newpos[tim-1]); for(int i=0;i
                    
                     =0; i--) { int t=newpos[i]; //printf("%d %d %d\n",t,p[t],p[p[t]]); if(!s[t]) { if(!se[p[t]]) { se[p[t]]=true; ans++; } s[t]=true; s[p[t]]=true; s[p[p[t]]]=true; } } return ans;}int main(){ int u,v,ans=0;; scanf("%d",&n); for(int i=1; i

转载于:https://www.cnblogs.com/jianrenfang/p/6666012.html

你可能感兴趣的文章