[BZOJ 2657] 旅游

发布于2016年02月27日 | 暂无评论 | 966阅读 | 树

题目描述

到了难得的暑假，为了庆祝小白在数学考试中取得的优异成绩，小蓝决定带小白出去旅游~~

经过一番抉择，两人决定将T国作为他们的目的地。T国的国土可以用一个凸N边形来表示，N个顶点表示N个入境/出境口。T国包含N-2个城市，每个城市都是顶点均为N边形顶点的三角形(换而言之，城市组成了关于T国的一个三角剖分)。两人的旅游路线可以看做是连接N个顶点中不相邻两点的线段。

为了能够买到最好的纪念品，小白希望旅游路线上经过的城市尽量多。作为小蓝的好友，你能帮帮小蓝吗？

输入格式

每个输入文件中仅包含一个测试数据。

第一行包含两个由空格隔开的正整数N，N的含义如题目所述。

接下来有N-2行，每行包含三个整数 p,q,r，表示该城市三角形的三个顶点的编号(T国的N个顶点按顺时间方向从1至n编号)。

输出格式

输出文件共包含1行，表示最多经过的城市数目。(一个城市被当做经过当且仅当其与线路有至少两个公共点)

题目解析

一开始还以为是计算几何，后来觉得这种不定形状的还是应该用图论解决。

解决此题，需要挖掘三角剖分的性质，一个三角剖分可以把一个凸 $n$ 边形划分成 $n-2$ 个区域，在凸 $n$ 边形内部应有 $n-3$ 条边。如果我们把每个城市当做一个点，相邻的区域连上一条边，毫无疑问，这样构成的图是连通的。所以这是一棵树。

转化成一棵树后问题便清晰了，题目所求即是树的直径。

/**************************************************************
    Problem: 2657
    User: frank_c1
    Language: C++
    Result: Accepted
    Time:1356 ms
    Memory:64556 kb
****************************************************************/
 
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <bitset>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define PER(i,a,b) for(int i=(a);i>=(b);i--)
#define RVC(i,S) for(int i=0;i<(S).size();i++)
#define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
       
template<class T> inline
void read(T& num) {
    bool start=false,neg=false;
    char c;
    num=0;
    while((c=getchar())!=EOF) {
        if(c=='-') start=neg=true;
        else if(c>='0' && c<='9') {
            start=true;
            num=num*10+c-'0';
        } else if(start) break;
    }
    if(neg) num=-num;
}
/*============ Header Template ============*/
 
struct edge {
    int next,to;
};
   
const int maxn=(int)(2e5)+5;
const int mo=5000000;
int fr[maxn];
int d[maxn];
LL key[mo];
int val[mo];
edge e[maxn<<1];
int n,tote=0;
   
inline void addone(int u,int v) {
    ++tote;
    e[tote].next=fr[u];fr[u]=tote;e[tote].to=v;
}
   
inline void addedge(int u,int v) {
    addone(u,v);addone(v,u);
}
 
inline LL idx(LL a,LL b) {return a*n+b;}
   
inline void check(int a,int b,int x) {
    LL k=idx(a,b),p=k % mo;
    while(key[p]!=0 && key[p]!=k) p=(p+1) % mo;
    if(key[p]==k) addedge(val[p],x);
    else key[p]=k,val[p]=x;
}
   
queue<int> Q;
inline int bfs(int s) {
    memset(d,-1,sizeof(d));
    int res=s;
    d[s]=0;
    Q.push(s);
    while(!Q.empty()) {
        int x=Q.front();Q.pop();
        RAL(i,x) if(d[e[i].to]==-1) {
            d[e[i].to]=d[x]+1;
            Q.push(e[i].to);
            if(d[e[i].to]>d[res]) res=e[i].to;
        }
    }
    return res;
}
   
int main() {
    int a,b,c;
    read(n);
    memset(fr,-1,sizeof(fr));
    REP(i,1,n-2) {
        read(a);read(b);read(c);
        if(b<a) swap(a,b);
        if(c<a) swap(a,c);
        if(c<b) swap(b,c);
        check(a,b,i);check(a,c,i);check(b,c,i); 
    }
    int s=bfs(1);
    printf("%d\n",d[bfs(s)]+1);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

/**************************************************************

Problem: 2657

User: frank_c1

Language: C++

Result: Accepted

Time:1356 ms

Memory:64556 kb

****************************************************************/

#include <set>

#include <map>

#include <queue>

#include <ctime>

#include <cmath>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <bitset>

#include <cstring>

#include <cstdlib>

#include <utility>

#include <iostream>

#include <algorithm>

#define REP(i,a,b) for(int i=(a);i<=(b);i++)

#define PER(i,a,b) for(int i=(a);i>=(b);i--)

#define RVC(i,S) for(int i=0;i<(S).size();i++)

#define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next)

using namespace std;

typedef long long LL;

typedef pair<int,int> pii;

template<class T> inline

void read(T& num) {

bool start=false,neg=false;

char c;

num=0;

while((c=getchar())!=EOF) {

if(c=='-') start=neg=true;

else if(c>='0' && c<='9') {

start=true;

num=num*10+c-'0';

} else if(start) break;

}

if(neg) num=-num;

}

/*============ Header Template ============*/

struct edge {

int next,to;

};

const int maxn=(int)(2e5)+5;

const int mo=5000000;

int fr[maxn];

int d[maxn];

LL key[mo];

int val[mo];

edge e[maxn<<1];

int n,tote=0;

inline void addone(int u,int v) {

++tote;

e[tote].next=fr[u];fr[u]=tote;e[tote].to=v;

}

inline void addedge(int u,int v) {

addone(u,v);addone(v,u);

}

inline LL idx(LL a,LL b) {return a*n+b;}

inline void check(int a,int b,int x) {

LL k=idx(a,b),p=k % mo;

while(key[p]!=0 && key[p]!=k) p=(p+1) % mo;

if(key[p]==k) addedge(val[p],x);

else key[p]=k,val[p]=x;

}

queue<int> Q;

inline int bfs(int s) {

memset(d,-1,sizeof(d));

int res=s;

d[s]=0;

Q.push(s);

while(!Q.empty()) {

int x=Q.front();Q.pop();

RAL(i,x) if(d[e[i].to]==-1) {

d[e[i].to]=d[x]+1;

Q.push(e[i].to);

if(d[e[i].to]>d[res]) res=e[i].to;

}

return res;

}

int main() {

int a,b,c;

read(n);

memset(fr,-1,sizeof(fr));

REP(i,1,n-2) {

read(a);read(b);read(c);

if(b<a) swap(a,b);

if(c<a) swap(a,c);

if(c<b) swap(b,c);

check(a,b,i);check(a,c,i);check(b,c,i);

}

int s=bfs(1);

printf("%d\n",d[bfs(s)]+1);

return 0;

}

AC. 梦想

[BZOJ 2657] 旅游

题目描述

输入格式

输出格式

题目解析

快速访问

随便看看

友情链接

标签