题目:
题意:给出n个点,n-1条边的一棵树。然后要在两个点上建立两个消防站。让全部点的到消防站最大距离的点的这个距离最小。
分析:首先先求这个树的直径。然后在树的直径的中点处把树分成两棵树。然后在把两棵树分别取中点的最大值就是ans值。
这个题目数据有点水了感觉。。。
AC代码:
#include#include #include #include #include #include using namespace std;const int N = 204000;int n;vector v[N];int vis[N],father[N];vector line;int BFS(int s,int flag){ queue 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 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 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 ans(one,tmp); return ans;}Node Importent(int fir,int sec){ Node pps; int ans = -1; pair 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