程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved