Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我觉得应该这么存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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator