題意：
? ? ?給你一棵樹，所有葉子節(jié)點(diǎn)都是客戶端，其他的都是服務(wù)器，然后問你最少在多少個服務(wù)器上安裝VOD能使所有的客戶端都能流暢的看視頻，流暢看視頻的條件是每個客戶端距離他最近的安裝VOD的服務(wù)器的距離不能超過k，而且題目已經(jīng)給你在一個服務(wù)器上安裝好了VOD。


思路：
? ? ?自己沒想出來，說下白書上的思路，第一個就是說當(dāng)遇到無根樹的時候，一般情況下把無根樹變成有根數(shù)會有利于問題的解決，然后這個題目就是把給定的VOD服務(wù)器變成了樹根，然后我們可以根據(jù)貪心策略，先處理深度最深的，安裝VOD是在當(dāng)前深度最深的上面第k個父親那安裝VOD這樣是為了盡可能多的去讓別的客戶端能用上這個VOD，然后就是模擬這個過程了，這個思路是白書上說的，我想了一陣子，只是感覺有道理，但并不能肯定他的正確性，說白了就是還沒弄清楚這樣為什么是對的，以后會重新編輯這篇博客。
? ? ?


#include<stdio.h>
#include<string.h>


#define N 1000+5
#define N_node 1000 + 5
#define N_edge 2000 + 10


typedef struct
{
? ?int to ,next;
}STAR;


STAR E[N_edge];
int list[N_node] ,tot;


int mark[N] ,mk[N] ,deep[N];
int dis[N][N] ,mer[N];


void add(int a ,int b)
{
? ?E[++tot].to = b;
? ?E[tot].next = list[a];
? ?list[a] = tot;
}


//deep mark


void DFS1(int s ,int fa)
{
? ?int mk = 0;
? ?for(int k = list[s] ;k ;k = E[k].next)
? ?{
? ? ? ?int to = E[k].to;
? ? ? ?if(to == fa) continue;
? ? ? ?mk = 1;
? ? ? ?mer[to] = s;
? ? ? ?deep[to] = deep[s] + 1;
? ? ? ?DFS1(to ,s);
? ?}
? ?mark[s] = !mk;
}


//dis
void DFS2(int sss ,int now ,int s ,int fa)
{
? ? for(int k = list[s] ;k ;k = E[k].next)
? ? {
? ? ? ? int to = E[k].to;
? ? ? ? if(to == fa) continue;
? ? ? ? dis[sss][to] = now;
? ? ? ? DFS2(sss ,now + 1 ,to ,s);
? ? }
}


int main ()
{
? ? int n ,s ,k ,i ,j ,t ,a ,b;
? ? scanf("%d" ,&t);
? ? while(t--)
? ? {
? ? ? ? scanf("%d %d %d" ,&n ,&s ,&k);
? ? ? ? memset(list ,0 ,sizeof(list)) ,tot = 1;
? ? ? ? for(i = 1 ;i < n ;i ++)
? ? ? ? {
? ? ? ? ? ? scanf("%d %d" ,&a ,&b);
? ? ? ? ? ? add(a ,b) ,add(b ,a);
? ? ? ? }
? ? ? ? for(i = 1 ;i <= n ;i ++) mer[i] = i;
? ? ? ? deep[s] = 0;
? ? ? ? DFS1(s ,-1);
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ?dis[i][i] = 0;
? ? ? ? ? ?DFS2(i ,1 ,i ,-1);
? ? ? ? }
? ? ? ? ?
? ? ? ? memset(mk ,0 ,sizeof(mk));
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? if(mark[i] && dis[s][i] <= k)?
? ? ? ? mk[i] = 1;
? ? ? ? int Ans = 0;
? ? ? ? while(1)
? ? ? ? {
? ? ? ? ? ? int mkid = 0 ,maxdeep = 0;
? ? ? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(!mark[i] || mk[i]) continue;
? ? ? ? ? ? ? ? if(maxdeep < deep[i])
? ? ? ? ? ? ? ? maxdeep = deep[i] ,mkid = i;
? ? ? ? ? ? }
? ? ? ? ? ? if(!mkid) break; ? ? ? ?
? ? ? ? ? ? Ans ++;
? ? ? ? ? ? int maxdis = 0 ,mknode = 0;
? ? ? ? ? ? mknode = mkid;
? ? ? ? ? ? for(i = 1 ;i <= k ;i ++)
? ? ? ? ? ? mknode = mer[mknode];
? ? ? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(!mark[i] || mk[i]) continue;
? ? ? ? ? ? ? ? if(dis[mknode][i] <= k) mk[i] = 1;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? printf("%d\n" ,Ans);
? ? }
? ? return 0;
} ? ?
? ? ? ??
? ? ? ? ? ?
? ? ? ? ? ??
? ? ? ??

總結(jié)

以上是生活随笔為你收集整理的LA3902网络的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。