大佬教程收集整理的这篇文章主要介绍了P6976 [NEERC2015]Distance on Triangulation，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

@H_450_1@tag:点分治，对偶图

思路

考虑分治解决问题，每次选一个三角形，处理经过这个三角形的询问，再递归下去。那么我们要做的就是使剩下部分尽量平均。

将原图的对偶图画出来，通俗来讲，就是把一个三角形当成一个点，再把有公共边的三角形连起来，会发现是一棵树(不考虑最外面的那个面)，于是发现这个过程就是点分治的过程。每次处理跨分治中心的询问，并递归解决其它询问

复杂度(O((n+q)logn))

建图

最关键的一步就是把对偶图弄出来。考虑用拓扑，每次将度数为 (2) 的点拿出来，那么这个点和它相连的两个点就构成了一个三角形，然后删掉这个点和这 (2) 条边。一直处理下去就可以找出所有三角形。

for(register int i=1; i<=n; i++) if(d[i]==2) q[++r] = i;
while(l<=n-2){   //一共只有n-2个三角形
    int x = q[l++]; vis[x] = true;
    int a=-1, b=-1;
    for(register int i=0, tp=to[x].size(); i<tp; i++) 
    	if(!vis[to[x][i]]) 
        	if(a==-1) a = to[x][i]; 
        	else b = to[x][i];
    t[++cnt] = (tri){x,a,b};
    d[a]--; d[b]--;
    if(d[a]==2) q[++r] = a; 
    if(d[b]==2) q[++r] = b;
}
    

建树的话，考虑每次处理到 (X) 的时候，当前三角形为 ((x,a,b))，那么当前三角形与父亲三角形相连的那条边一定是 ((a,b))，就把这个三角形记在边 ((a,b)) 上(我比较懒直接用 (map))。然后处理到 ((x,a,b)) 时看一看每条边是否接了一个三角形。

if(mp[make(x,a)]) T.Add_Edge(cnt,mp[make(x,a)]);
if(mp[make(x,b)]) T.Add_Edge(cnt,mp[make(x,b)]);
if(mp[make(a,b)]) T.Add_Edge(cnt,mp[make(a,b)]);
else mp[make(a,b)] = cnt;

分治

分治过程和点分治大同小异，这里主要讲一个直接求出最短路的方法。(当然你也可以直接bfs三遍，不过常数有点大)

先手动赋值根结点对应的三个点的(dis)数组。

假设 (dfs) 到了 (X)，那么 (X) 对应的三角形 ((A,B,C)) 一定有两个顶点是之前处理过的，所以只需要找出没有处理的那个顶点( 设为 (C) )，然后设 (dis_C=min{dis_A,dis_B}+1) 即可。

/*
bel[x]表示x属于哪个子树
::bel[x] 的意思就是 bel[x]，只不过这里和函数内部的bel重名了，所以要用::去调用
*/
if(!::bel[t[x].a]) np = t[x].a;
if(!::bel[t[x].b]) np = t[x].b;
if(!::bel[t[x].c]) np = t[x].c;
::bel[np] = bel; p[++top] = np;
for(register int i=0; i<3; i++) 
    dis[np][i] = inf,
    dis[np][i] = min(min(dis[t[x].a][i],dis[t[x].b][i]),dis[t[x].c][i])+1;

杂项

这道题写对拍造数据可能不太好造，提供一个思路：用双向链表把 (1) ~ (n) 串起来，每次随机一个还在的点 (X)，把 (X) 左右两个点 (l) 和 (r) 连起来(即输出 (l r))，然后删掉 (X)。

完整代码

大佬总结

以上是大佬教程为你收集整理的P6976 [NEERC2015]Distance on Triangulation全部内容，希望文章能够帮你解决P6976 [NEERC2015]Distance on Triangulation所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。