首页 > 代码库 > ZOJ Problem Set - 3820 Building Fire Stations 【树的直径 + 操作 】
ZOJ Problem Set - 3820 Building Fire Stations 【树的直径 + 操作 】
题目:
problemId=5374" target="_blank">ZOJ Problem Set - 3820 Building Fire Stations
题意:给出n个点,n-1条边的一棵树。然后要在两个点上建立两个消防站。让全部点的到消防站最大距离的点的这个距离最小。
分析:首先先求这个树的直径。然后在树的直径的中点处把树分成两棵树。然后在把两棵树分别取中点的最大值就是ans值。
这个题目数据有点水了感觉。。。
AC代码:
#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <cstring> #include <queue> using namespace std; const int N = 204000; int n; vector<int> v[N]; int vis[N],father[N]; vector<int> line; int BFS(int s,int flag) { queue<int> q; int e=s; line.clear(); memset(vis,0,sizeof(vis)); memset(father,-1,sizeof(father)); vis[flag]=1; q.push(s); vis[s]=1; int ans=1; while(!q.empty()) { int f=q.front(); q.pop(); for(int i=0; i<v[f].size(); i++){ int k=v[f][i]; if(vis[k]) continue; vis[k]=vis[f]+1; father[k]=f; if(vis[k]>ans){ e=k; ans=vis[k]; } q.push(k); } } for(int i=e;i!=-1;i=father[i]) line.push_back(i); return e; } struct Node { int one,two,ans; }; void print() //输出 { for(int i = 0;i<line.size();i++) { printf("x%d ",line[i]); } printf("\n"); } pair<int,int> Yougth(int s,int t) { int p1 = BFS(s,t); int p2 = BFS(p1,t); int len = line.size(); int one = line[len/2]; int tmp = len/2; pair<int,int> ans(one,tmp); return ans; } Node Importent(int fir,int sec) { Node pps; int ans = -1; pair<int,int> tt = Yougth(fir,sec); pps.one = tt.first; ans = max(ans,tt.second); tt = Yougth(sec,fir); pps.two = tt.first; ans = max(ans , tt.second); pps.ans = ans; return pps; } void solve() { Node pps,ans2; int p1 = BFS(1,n+1); int p2 = BFS(p1,n+1); int len = line.size()/2; int a = line[len-1],b = line[len] , c = line[len+1]; if(line.size()%2==0) { pps = Importent(a,b); } else { pps = Importent(a,b); ans2 = Importent(b,c); if(ans2.ans<pps.ans) //取小的。可是好像没有这种数据 pps = ans2; } printf("%d %d %d\n",pps.ans,pps.one,pps.two); } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=0;i<n-1;i++) { int x,y; scanf("%d%d",&x,&y); v[x].push_back(y); v[y].push_back(x); } solve(); for(int i=0;i<=n;i++) v[i].clear(); } return 0; }
ZOJ Problem Set - 3820 Building Fire Stations 【树的直径 + 操作 】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。