BZOJ2657: [Zjoi2012]旅游(journey) (树形DP)
2024-09-30 20:55:51
题意:一个三角划分的凸多边形 画一条对角线 穿过最多的三角形
题解:把每一个三角形看作一个点 如果某条边是两个三角形的公共边 那么就把这两个三角形连边
然后问题就转化为求树上的最长链了 就当求个直径就完了
#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 ;
}
最新文章
- Cheatsheet: 2016 05.01 ~ 05.31
- java中调用xml的方法:DocumentBuilderFactory
- 【转】HBase原理和设计
- [深入浅出Windows 10]QuickCharts图表控件库解析
- 构建高性能的ASP.NET应用程序
- 深入理解CSS中的层叠上下文和层叠顺序
- vs 2012 智能提示后为何不能 直接按enter键把提示的内容输入
- nodejs学习--express篇
- cocos2d-x混合BlendFunc的使用
- mvc 生成输出url
- java 执行bat文件 并输出信息
- SpringMVC静态文件(图片)访问+js访问 简单小例子
- Mpg123源代码详解
- C# 代码补全
- 【转】使用Eclipse,将鼠标放在相应方法或字段等元素上时,无法显示提示
- 【转】odoo nginx 配置
- C# 多线程调用静态方法或者静态实例中的同一个方法-方法内部的变量是线程安全的
- MongoDB pymongo模块 插入数据
- python if __name__ == &#39;main&#39; 的作用和原理()
- c#中的数组、ArrayList、List区别【转】