注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2657][Zjoi2012]旅游(journey)  

2015-03-21 11:26:48|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2657: [Zjoi2012]旅游(journey)

明白了就知道是水题……
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 2E5+100;
int n,m,ans,en;
int scan(){
char cc=' ';int re=0,fh=1;while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){re=re*10+cc-'0';cc=getchar();}return re*fh;
}
struct Edge{int a,b,i;Edge(int aa=0,int bb=0,int ii=0){a=aa;b=bb;i=ii;if(a>b)swap(a,b);}}ed[N*3];
bool operator < (const Edge&a,const Edge&b){return a.a==b.a?a.b<b.b:a.a<b.a;}
bool operator == (const Edge&a,const Edge&b){return a.a==b.a&&a.b==b.b;}
struct Point{
Point(){next = NULL;}
int d;Point *next;
void push(int a){
Point *l = new Point;
l->d = a;l->next = next;
next = l;
}
}point[N];
int fa[N],dis[N];
queue<int>dui;
void solve(int p=1){
dui.push(p);
while(!dui.empty()){
int now = dui.front();dui.pop();
if(dis[now] > dis[ans])ans=now;
for(Point *i = point[now].next;i!=NULL;i=i->next)
if(i->d != fa[now]){
fa[i->d] = now;
dis[i->d] = dis[now]+1;
dui.push(i->d);
}fa[now]=0;
}
}
int main(){
int i,j,a,b,c;
n = scan()-2;
for(i=1;i<=n;i++){
a=scan();b=scan();c=scan();
ed[++en]=Edge(a,b,i);
ed[++en]=Edge(b,c,i);
ed[++en]=Edge(a,c,i);
}
sort(ed+1,ed+1+en);
for(i=1;i<en;i++)
if(ed[i]==ed[i+1]){
a=ed[i].i;b=ed[i+1].i;
point[a].push(b);
point[b].push(a);
i++;
}
solve();
for(i=1;i<=n;i++)dis[i]=0;
solve(ans);
printf("%d\n",dis[ans]+1);
return 0;
}

题解:
把区域看成点,共用边看成连接两个区域的边。
因为是凸多边形的三角剖分所以显然是个树,然后题目就变成了找树的直径……bfs两遍就完了
  评论这张
 
阅读(286)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017