Why so serious? --[NKU]schindlerlee

2010年02月13日星期六.sgu174 并查集+二叉搜索树

2010年02月13日星期六.sgu174
sgu174:并查集+二叉搜索树
说说题意吧。就是每次给出两个点,这两个点代表一条线段,如果这一条线段能和已经存在的线
段构成一个封闭多边形,那么就输出这是第几条线段。

很自然的能想到并查集,所差的就是为每一个点赋予一个唯一的编号。
如果线性的查找已经处理过的点,那么就每次查询的复杂度就是O(n).
而有n个这样的查询。当n如此大的时候,n^2的算法显然会超时。

我们需要提高每次查询的复杂度。
其实很容易就能想到二叉搜索树。不想写的话可以直接使用stl中的map,map是红黑树的实现,如
果不怕常数复杂度的话,这是一个很好的想法。

还有就是并查集,并查集需要加上路径压缩,不然很容易超时。

 1 
 2 const int N = 400010;
 3 struct point_t {
 4     int x,y;
 5     point_t(){}
 6     point_t(int a,int b){x = a,y = b;}
 7 }a,b;一bool operator < (point_t a,point_t b)
 8 {
 9   if (a.x != b.x) {
10       return a.x < b.x;
11   }
12   return a.y < b.y;
13 }
14 map<point_t,int> g;
15 int n, p[N],rank[N];
16 
17 int findset(int x)
18 {
19   if (p[x] != x) {
20       p[x] = findset(p[x]);
21   }
22   return p[x];
23 }
24 //http://www.cppblog.com/schindlerlee
25 bool unionset(int x,int y)
26 {
27   x = findset(x);
28   y = findset(y);
29   if (x == y) { return true; }
30   if (rank[x] > rank[y]) {
31       p[y] = x;
32   } else if (rank[x] < rank[y]) {
33       p[x] = y;
34   } else if (rank[x] == rank[y]) {
35       p[x] = y;
36       rank[y]++;
37   }
38   return false;
39 }
40 
41 int main()
42 {
43   int i,ia,ib;
44   scanf("%d",&n);
45   for (i = 0;i < N;i++) { p[i] = i; }
46   for (i = 1;i <= n;i++) {
47       scanf("%d%d%d%d",&a.x,&a.y,&b.x,&b.y);
48       if ((ia = g[a]) == 0) { ia = g[a] = i << 1; } //from 1
49       if ((ib = g[b]) == 0) { ib = g[b] = (i << 1+ 1; }
50       if (unionset(ia,ib)) {
51           printf("%d\n",i);
52           break;
53       }
54   }
55   if (i > n) {
56       printf("0\n");
57   }
58   return 0;
59 }
60 


posted on 2010-02-14 00:38 schindlerlee 阅读(1553) 评论(0)  编辑 收藏 引用 所属分类: 解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理