程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> zoj 3820 Building Fire Stations The 2014 ACM-ICPC Asia Mudanjiang Regional Contest B題樹的直徑

zoj 3820 Building Fire Stations The 2014 ACM-ICPC Asia Mudanjiang Regional Contest B題樹的直徑

編輯：C++入門知識

zoj 3820 Building Fire Stations The 2014 ACM-ICPC Asia Mudanjiang Regional Contest B題樹的直徑

題意：n個點的樹，給出n-1條邊，每條邊長都是1，兩個點建立防火站，使得其他點到防火站的最遠距離最短。

思路：先求出樹的直徑，直徑上的所有點都存到一個數組裡。如果直徑是奇數，把中間的那條邊刪去；如果是偶數，把中間的點，分

到兩邊的子樹。對兩個子樹分別求樹直徑的中點即可。詳見代碼：

/*********************************************************
  file name: zoj3820.cpp
  author : kereo
  create time:  2015年02月08日 星期日 15時31分32秒
*********************************************************/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=100+50;
const int MAXN=200000+50;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=1000000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define PII pair
#define mk(x,y) make_pair((x),(y))
int n,edge_cnt,top;
int head[MAXN],vis[MAXN],d[MAXN],fa[MAXN],s[MAXN];
struct Edge{
    int v,next;
}edge[MAXN<<1];
void init(){
    edge_cnt=0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v){
    edge[edge_cnt].v=v; 
    edge[edge_cnt].next=head[u]; head[u]=edge_cnt++;
}
int bfs(int st){
    int ans=st;
    queueQ; Q.push(st);
    vis[st]=1; d[st]=0; fa[st]=-1;
    while(!Q.empty()){
        int u=Q.front(); Q.pop();
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].v;
            if(vis[v])
                continue;
            vis[v]=1; d[v]=d[u]+1; fa[v]=u;
            if(d[v]>d[ans])
                ans=v;
            Q.push(v);
        }
    }
    top=0;
    int u=ans;
    while(u!=-1){
        s[top++]=u; u=fa[u];
    }
    return ans;
}
int main(){
    //freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--){
        init();
        scanf("%d",&n);
        for(int i=1;i

C++入門知識

hdu 1016 Prime Ring Problem（深度優先搜索），hdu深度優先搜索

hdu 1016 Prime Ring Problem（深度

POJ 2003 Hire and Fire (多重鏈表樹結構好題)

POJ 2003 Hire and Fire (多重鏈表樹

大話設計模式C++實現-第15章-抽象工廠模式

大話設計模式C++實現-第15章-抽象工廠模式一、UM

圖文例解C++類的多重繼承與虛擬繼承

　　在過去的學習中，我們始終接觸的單個類的繼續，但是

C++ Builder 初學問與答(八)

　　8.圖形類組件　　59）問：Windows是一個

Linux下運行C++程序出現"段錯誤(核心已轉儲)"的原因，linux轉儲

Linux下運行C++程序出現"段錯誤(核心已轉儲

zoj 3820 Building Fire Stations The 2014 ACM-ICPC Asia Mudanjiang Regional Contest B題 樹的直徑

zoj 3820 Building Fire Stations The 2014 ACM-ICPC Asia Mudanjiang Regional Contest B題 樹的直徑

zoj 3820 Building Fire Stations The 2014 ACM-ICPC Asia Mudanjiang Regional Contest B題樹的直徑

zoj 3820 Building Fire Stations The 2014 ACM-ICPC Asia Mudanjiang Regional Contest B題樹的直徑