海东高端网站建设价格,哈尔滨信息网租房信息,iframe 网站前台模板,网站建设书籍论文problem
写的什么jb题意#xff01;这个语文水平。。。。
洛谷的一堆题解看下来也没懂他们懂得题目大意#xff0c;真是给我蚌埠住了
luogu评测链接
一句话题意#xff1a;给定一个三角剖分#xff0c;求任意两顶点穿过的最多三角形个数#xff08;只经过某三角形顶点…problem
写的什么jb题意这个语文水平。。。。
洛谷的一堆题解看下来也没懂他们懂得题目大意真是给我蚌埠住了
luogu评测链接
一句话题意给定一个三角剖分求任意两顶点穿过的最多三角形个数只经过某三角形顶点则不算穿过该三角形
solution
一般三角剖分就先往转化成树的方向思考。—— Quack\text{Quack}Quack。
一条线穿过的三角形相邻两个肯定是有邻边的。
我们把三角形即城市看成一个点与其有邻边的城市之间就连一条边。
那么会发现这个穿的路线就是在这个树上跑一条链。
最大化个数就是最长化链长那要求的就是这个树的直径。
所以这道题的难点在于你读懂题目了吗
这个连边后一定是个树不会出现环。
n−2n-2n−2 个三角形只需要 n−3n-3n−3 条边就可以剖分出来。
且这个三角剖分的三个点都是顶点相当于是生成图上的一条边n−2n-2n−2 个城市点n−3n-3n−3 条边。
生成环意味着有一堆三角形围住了一个城市点这显然不可能。
code
#include bits/stdc.h
using namespace std;
#define maxn 200005
map pair int, int , int mp;
vector int G[maxn];
int n, ans;
int dp[maxn];void dfs( int u, int fa ) {dp[u] 1;for( int v : G[u] ) {if( v fa ) continue;else dfs( v, u );ans max( ans, dp[u] dp[v] );dp[u] max( dp[u], dp[v] 1 );}
}int main() {scanf( %d, n );int x[5];for( int i 1;i n - 2;i ) {for( int j 1;j 3;j ) scanf( %d, x[j] );sort( x 1, x 4 );for( int j 1;j 3;j )for( int k j 1;k 3;k )if( ! mp[make_pair( x[j], x[k] )] )mp[make_pair( x[j], x[k] )] i;else {G[i].push_back( mp[make_pair( x[j], x[k] )] );G[mp[make_pair( x[j], x[k] )]].push_back( i );}}dfs( 1, 0 );printf( %d\n, ans );return 0;
}
