1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> using namespace std; #define MAXN 200005 struct nodeType{ vector<int> to; int dep; } node[MAXN]; void init_node(int n,bool clearljb){ for (int i = 1; i <= n; i++) { if(clearljb) node[i].to.clear(); node[i].dep = 1; } } vector<int> tdr; int prevNode[MAXN]; bool vis[MAXN]; int bfs(int n,bool metaMode,int src,bool gentdr,int blocked){ //0 for meta 1 for tdim //make blocked 0 if you do not want to split init_node(n,false); memset(vis, 0, sizeof(vis)); memset(prevNode, 0, sizeof(prevNode)); queue<int> q; q.push(src); int last = 0,maxdep = 0; while (!q.empty()) { nodeType &now = node[q.front()]; vis[q.front()] = true; if (now.dep > maxdep) { maxdep = now.dep; last = q.front(); } for (int i = 0; i < now.to.size(); i++) { if (vis[now.to[i]] || now.to[i] == blocked) { continue; } node[now.to[i]].dep = now.dep+1; q.push(now.to[i]); prevNode[now.to[i]] = q.front(); } q.pop(); } if (metaMode) { return last; }else { if (gentdr) { tdr.clear(); int tmp = last; while (src != tmp) { tdr.push_back(tmp); tmp = prevNode[tmp]; } tdr.push_back(src); } return maxdep; } } int main(){ int casecnt; cin >> casecnt; while (casecnt--) { int n; cin >> n; init_node(n,true); for (int i = 1; i <= n-1; i++) { int a = 0,b = 0; scanf(" %d %d",&a,&b); node[a].to.push_back(b); node[b].to.push_back(a); } int seed = rand()%n+1; int meta = bfs(n, true, seed,false,0); int tdim = bfs(n, false, meta, true,0); int lans = 0,rans = 0,dis = 0; if (tdim % 2) { vector<int> origtdr = tdr; int center = (tdim-1)/2; //odd situ1 int lmeta1 = bfs(n, true, origtdr[0], false, origtdr[center]); int ltdim1 = bfs(n, false, lmeta1, true, origtdr[center]); int lpos1 = tdr[ltdim1/2]; int rmeta1 = bfs(n, true, origtdr[tdim-1], false, origtdr[center-1]); int rtdim1 = bfs(n, false, rmeta1, true, origtdr[center-1]); int rpos1 = tdr[rtdim1/2]; int judge1 = max(ltdim1/2,rtdim1/2); //odd situ2 int lmeta2 = bfs(n, true, origtdr[0], false, origtdr[center+1]); int ltdim2 = bfs(n, false, lmeta2, true, origtdr[center+1]); int lpos2 = tdr[ltdim2/2]; int rmeta2 = bfs(n, true, origtdr[tdim-1], false,origtdr[center]); int rtdim2 = bfs(n, false, rmeta2, true, origtdr[center]); int rpos2 = tdr[rtdim2/2]; int judge2 = max(ltdim2/2,rtdim2/2); //judge if (judge1 > judge2) { //2 is good lans = lpos2; rans = rpos2; dis = judge2; }else{ //1 is good lans = lpos1; rans = rpos1; dis = judge1; } }else{ //even situ int lend = tdr[tdim/2-1]; int rend = tdr[tdim/2]; //run left int lmeta = bfs(n, true, tdr[0], false,rend); //run right int rmeta = bfs(n, true, tdr[tdim-1], false, lend); int ltdim = bfs(n, false, lmeta, true, rend); lans = tdr[ltdim/2]; int rtdim = bfs(n, false, rmeta, true, lend); rans = tdr[rtdim/2]; dis = max(ltdim/2,rtdim/2); } cout << dis << ' ' << lans << ' ' << rans << ' ' << endl; } return 0; } |
SXBK的一个题(对我现在的水平来说)
其实是这样,对于一棵树,在上面建1个消防站,最优位置在直径中心,建立两个消防站呢?其实可以把整个大树分成两个小树,在每个小树自己的直径的中心建立消防站就搞定了,在分树的时候,如果发生分歧(如果直径有奇数个点,就会出现这种分歧情况,如果有偶数个节点,中央节点有两个,直接从两个节点的中央裂开就行,不会产生分歧),这时候我把中央节点上连接的那些节点中除了直径上的两点之外的那些节点都叫做中立节点,我们只要进行两次讨论,一次把这些中立节点分入左半树,求出这种分法中左右半树的直径,然后把左右直径的最大值当成接下来判定哪个方法更好的基准(因为我们要的是最长距离的最小值),然后再把这些中立节点分入右半树,搞出相应的解,接下来我们比较刚才保存下来的基准,哪个小要哪种方案,这样我们就把最终的解搞出来了。
我觉得其实这种思路还可以推广,如果建立3个,4个乃至n个,我们也可以切割树求直径来搞。
然后切树是,我们可以通过把某个点“屏蔽”,来实现不会让dfs进入另一半子树的目的。
其实这个题还可以通过枚举大直径上的两点求出最优解来解决,思路也是比较清晰的。