程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> zoj 3820 Building Fire Stations The 2014 ACM

zoj 3820 Building Fire Stations The 2014 ACM

編輯：關於C++

題意：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++

筆試題32. LeetCode OJ (19)

終於碰見了和數據結構相關的題目了，這也意味著復雜度在增加。來

如何正確理解C++默認構造函數

對於C++默認構造函數，我曾經有兩點誤解：類如

與/或表達式化簡

一、問題的提出假如我們有如下所示的與/或表達式

[LeetCode]Binary Tree Maximum Path Sum

【題目】 Given a binary tree, fi

LeetCode 14 Longest Common Prefix（最長公共前綴）

翻譯寫一個函數（或方法）來尋找一個字符串數組中的最長公共前綴

C++開源日志庫Glog的使用（VS2010）

Glog地址：https://github.com/goog