pku1456 Supermarket

pku1456 Supermarket

一道经典贪心题，用并查集来优化。

万恶的pku，这题pascal读入必须用seekeof判断是否读完数据，否则WA死你。。。

 1 program pku1456(input,output);
 2 var
 3     x,w        :array[0..11000] of longint;
 4     f        :array[0..11000] of longint;
 5     n        :longint;
 6     answer    :longint;
 7 procedure swap(var aa,bb:longint);
 8 var
 9     tt:longint;
10 begin
11     tt:=aa;
12     aa:=bb;
13     bb:=tt;
14 end;
15 procedure sort(p,q:longint);
16 var
17     i,j,m:longint;
18 begin
19     i:=p;
20     j:=q;
21     m:=w[(i+j)>>1];
22     repeat
23         while w[i]>m do
24             inc(i);
25         while w[j]<m do
26             dec(j);
27         if i<=j then
28         begin
29             swap(w[i],w[j]);
30             swap(x[i],x[j]);
31             inc(i);
32             dec(j);
33         end;
34     until i>j;
35     if i<q then sort(i,q);
36     if j>p then sort(p,j);
37 end;
38 function getfather(x:longint):longint;
39 begin
40     if f[x]=x then
41         exit(f[x]);
42     f[x]:=getfather(f[x]);
43     exit(f[x]);
44 end;
45 procedure init;
46 var
47     i:longint;
48 begin
49     read(n);
50     for i:=1 to n do
51         read(w[i],x[i]);
52     for i:=0 to 10000 do
53         f[i]:=i;
54 end;
55 procedure main;
56 var
57     i,xx:longint;
58 begin
59     sort(1,n);
60     answer:=0;
61     for i:=1 to n do
62     begin
63         xx:=getfather(x[i]);
64         if xx=0 then
65             continue;
66         inc(answer,w[i]);
67         f[xx]:=xx-1;
68     end;
69     writeln(answer);
70 end;
71 begin
72     while not seekeof do
73     begin
74         init;
75         main;
76     end;
77 end.

转载于:.html