[bzoj] 2657 ZJOI2012 旅游 || bfs

原题

题意：

一个多边形，三角剖分，求一条对角线最多能经过多少三角形

题解：

因为不涉及坐标之类的，所以根几何肯定一点关系都没有。

我们会发现，对于有共边的两个三角形，可以被同一条线穿过，而这就相当于这两个三角形之间有边。然后因为是多边形的三角剖分，所以最后只会有n-1条边。这样我们得到的就是一棵树了！

然后呢，因为我们要求的是任意一条对角线经过最多的城市个数，显然，这就是要求树上最长的一条路径，也就是树的直径了！

至于O(log)连边，考虑用pair将边和所属编号记录在map里，查询时连边即可（因为一条边最多被覆盖两次，所以想变快可以在该边被覆盖后将map中erase）

洛谷不开O2很慢……开O2很快……

#include<cstdio>

#include<queue>

#include<map>

#include<cstring>

#define N 200010

#define MP(x,y) make_pair(x,y)

using namespace std;

int n,dep[N],t,cnt=1,head[N];

queue <int> q;

bool vis[N];

map < pair<int,int> , int > mp;

struct hhh

{

    int to,next;

}edge[2*N];

int read()

{

    int ans=0,fu=1;

    char j=getchar();

    for (;j<'0' || j>'9';j=getchar()) if (j=='-') fu=-1;

    for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';

    return ans*fu;

}

void add(int u,int v)

{

    edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;

    edge[cnt].to=u;edge[cnt].next=head[v];head[v]=cnt++;

}

int bfs(int s)

{

    dep[s]=1;

    memset(vis,0,sizeof(vis));

    vis[s]=1;

    int mx=0;

    q.push(s);

    while (!q.empty())

    {

	int r=q.front();

	q.pop();

	if (dep[r]>mx) t=r,mx=dep[r];

	for (int i=head[r];i;i=edge[i].next)

	{

	    if (vis[edge[i].to]) continue;

	    q.push(edge[i].to);

	    vis[edge[i].to]=1;

	    dep[edge[i].to]=dep[r]+1;

	}

    }

    return mx;

}

int main()

{

    n=read();

    for (int i=1,a,b,c;i<n-1;i++)

    {

	a=read(),b=read(),c=read();

	if (mp[MP(min(a,b),max(a,b))]) add(mp[MP(min(a,b),max(a,b))],i);

	else mp[MP(min(a,b),max(a,b))]=i;

	if (mp[MP(min(a,c),max(a,c))]) add(mp[MP(min(a,c),max(a,c))],i);

	else mp[MP(min(a,c),max(a,c))]=i;

	if (mp[MP(min(c,b),max(b,c))]) add(mp[MP(min(c,b),max(b,c))],i);

	else mp[MP(min(c,b),max(b,c))]=i;

    }

    bfs(1);

    printf("%d\n",bfs(t));

    return 0;

}

巴特西

[bzoj] 2657 ZJOI2012 旅游 || bfs

原题

最新文章

热门文章