Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我觉得应该这么存

Posted by guoshi3 at 2008-08-10 13:30:03 on Problem 1161
In Reply To:这题图怎么存啊??我是菜鸟,一点头绪都没有.... Posted by:dzs8819 at 2007-07-21 16:58:27
把region当成节点,若两region相连距离就是1,否则是max

判断两region是否相连,可在读入的时候判断。利用到一个性质,就是一条边只能被两个region所共有。并且题目的input是给出每个region的border上的点,即相当于给出了围着该region的边。input保证了这么一点:除了outside region外所有region的border上的点是按顺时针顺序给出,而outside的是按逆时针。这样一个边两个端点出现在两个region中的顺序必然是相反的。

所以用一个数组a[i][j]存对于以i,j为端点的边属于哪个region。
例如对于region i,给出的border上的点有a,b,c;即三条边(a,b),(b,c),(c,a),对于a,b,先检查a[b][a]是否为0,若不为0,则d[i][a[b][a]]=d[a[b][a]][i]=1;若为0,则a[a][b]=i;

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator