题意:一个三角划分的凸多边形 画一条对角线 穿过最多的三角形

题解:把每一个三角形看作一个点 如果某条边是两个三角形的公共边 那么就把这两个三角形连边

   然后问题就转化为求树上的最长链了 就当求个直径就完了

#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std; struct node
{
int x, y, id;
}E[]; bool cmp(node A, node B)
{
if(A.x == B.x) return A.y < B.y;
else return A.x < B.x;
} int n, zd, rt;
int to[];
int dis[];
int nex[];
int head[]; void dfs(int x, int fa)
{
int c = head[x];
for(int i = c; i; i = nex[i])
{
int v = to[i];
if(v == fa) continue;
dis[v] = dis[x] + ;
if(dis[v] > zd) rt = v, zd = dis[v];
dfs(v, x);
}
} int main()
{
zd = rt = ;
scanf("%d", &n);
int cnt = ; for(int i = ; i <= n - ; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if(a < b) swap(a, b);
if(b < c) swap(b, c);
if(a < b) swap(a, b);
E[++cnt].x = a; E[cnt].y = b; E[cnt].id = i;
E[++cnt].x = b; E[cnt].y = c; E[cnt].id = i;
E[++cnt].x = a; E[cnt].y = c; E[cnt].id = i;
}
sort(E + , E + + cnt, cmp); int cn = ;
for(int i = ; i <= cnt; i++)
{
if(E[i].x == E[i - ].x && E[i].y == E[i - ].y)
{
int u = E[i].id; int v = E[i - ].id;
to[++cn] = u; nex[cn] = head[v]; head[v] = cn;
to[++cn] = v; nex[cn] = head[u]; head[u] = cn;
}
}
dfs(, -);
zd = ; int l = rt;
dis[rt] = ;
dfs(rt, -);
printf("%d\n", zd);
return ;
}

最新文章

  1. Cheatsheet: 2016 05.01 ~ 05.31
  2. java中调用xml的方法:DocumentBuilderFactory
  3. 【转】HBase原理和设计
  4. [深入浅出Windows 10]QuickCharts图表控件库解析
  5. 构建高性能的ASP.NET应用程序
  6. 深入理解CSS中的层叠上下文和层叠顺序
  7. vs 2012 智能提示后为何不能 直接按enter键把提示的内容输入
  8. nodejs学习--express篇
  9. cocos2d-x混合BlendFunc的使用
  10. mvc 生成输出url
  11. java 执行bat文件 并输出信息
  12. SpringMVC静态文件(图片)访问+js访问 简单小例子
  13. Mpg123源代码详解
  14. C# 代码补全
  15. 【转】使用Eclipse,将鼠标放在相应方法或字段等元素上时,无法显示提示
  16. 【转】odoo nginx 配置
  17. C# 多线程调用静态方法或者静态实例中的同一个方法-方法内部的变量是线程安全的
  18. MongoDB pymongo模块 插入数据
  19. python if __name__ == &#39;main&#39; 的作用和原理()
  20. c#中的数组、ArrayList、List区别【转】

热门文章

  1. OpenStack QA
  2. 仰视源代码,实现strcmp
  3. gcc的搜索路径,头文件和库
  4. 并不对劲的[noi2006]网络收费
  5. 符号修饰与函数签名、extern “C”(转载)
  6. J20180116
  7. bzoj 1753: [Usaco2005 qua]Who&#39;s in the Middle【排序】
  8. [Swift]Array(数组)扩展
  9. Cmake编译protobuf
  10. Hexo 添加Live2D看板娘