|
COMNET - VOI2013 8 năm trước
|
(+0)
|
Tư tưởng của mình:
- Đầu tiên dùng 3 mảng uu,vv,ww,css(chỉ số) lưu thông tin về đồ thị ban đầu.
- Với mỗi giả định, gán u,v,w,cs cho uu,vv,ww,css; thay đổi các thông số, rồi kruskal lần 1 (quicksort và find-union). Đến lần kruskal thứ 2 mình loại bỏ cạnh k bằng cách là duyệt đến cạnh nào có cs[i]=k (sau khi đã sắp xếp) thì không union mà bỏ qua.
- min lưu trọng số cây khung nhỏ nhất của đồ thị sau khi thay đổi mà CÓ cạnh k, sum lưu trọng số cây khung nhỏ nhất sau khi thay đổi mà KHÔNG CÓ cạnh k, dinh dùng để kiểm tra tính thông suốt sau khi loại bỏ cạnh k.
- Nếu dinh=n hoặc sum=min thì cạnh k không tiềm năng và nếu không thì cạnh k tiềm năng
Mình nghĩ là cách làm này đúng.
Đây là code của mình, không biết là bị WA hay TLE mà chỉ được 40 điểm.
Mọi người giúp mình với ạ
Code: | program comnet;
type
iii=longint;
bfg=int64;
const
fi='';
fo='';
maxn=100000;
maxm=1000000;
var
uu,vv,u,v: array[1..maxm] of iii;
ww,w: array[1..maxm] of bfg;
cs,css: array[1..maxm] of iii;
tt,t: array[1..maxn] of iii;
n,m,q: iii;
f1,f2: text;
procedure openfile;
begin
assign(f1,fi); reset(f1);
assign(f2,fo); rewrite(f2);
end;
procedure closefile;
begin
close(f1); close(f2);
end;
procedure inn;
var
i: iii;
begin
readln(f1,n,m,q);
for i:=1 to m do readln(f1,uu[i],vv[i],ww[i]);
for i:=1 to m do css[i]:=i;
for i:=1 to n do tt[i]:=i;
end;
procedure swap(i,j: iii);
var
tg: iii;
tg2: bfg;
begin
tg:=u[i]; u[i]:=u[j]; u[j]:=tg;
tg:=v[i]; v[i]:=v[j]; v[j]:=tg;
tg:=cs[i]; cs[i]:=cs[j]; cs[j]:=tg;
tg2:=w[i]; w[i]:=w[j]; w[j]:=tg2;
end;
procedure qs(l,r: iii);
var
i,j: iii;
key: bfg;
begin
if l>=r then exit;
i:=l; j:=r; key:=w[i+ random(j-i)+1];
repeat
while w[i]<key do inc(i);
while w[j]>key do dec(j);
if i<=j then
begin
swap(i,j);
inc(i); dec(j);
end;
until i>j;
qs(l,j); qs(i,r);
end;
function find(x: iii): iii;
begin
while x<>t[x] do x:=t[x];
end;
function union(x,y: iii): boolean;
begin
x:=find(x); y:=find(y);
if x=y then exit(false);
if x>y then t[x]:=y else t[y]:=x;
exit(true);
end;
procedure process;
var
ii,i,tp,k,s,dinh: iii;
cp,min,sum: bfg;
begin
for ii:=1 to q do
begin
read(f1,k,s);
u:=uu; v:=vv; w:=ww; cs:=css; t:=tt;
for i:=1 to s do
begin
read(f1,tp,cp);
w[tp]:=cp;
end;
qs(1,m); min:=0;
for i:=1 to m do
if union(u[i],v[i]) then
inc(min,w[i]);
sum:=0; dinh:=1;
t:=tt;
for i:=1 to m do
if (union(u[i],v[i])) and (cs[i]<>k) then
begin
inc(dinh);
inc(sum,w[i]);
end;
if (dinh=n) and (sum=min) then writeln(f2,'YES') else writeln(f2,'NO');
end;
end;
procedure main;
var
i,test: iii;
begin
readln(f1,test);
for i:=1 to test do
begin
inn;
process;
end;
end;
begin
openfile;
main;
closefile;
end.
|
|
|
|
Đã lưu IP
|
|
Đã khóa chức năng gửi bài. |
|
Trả lời: COMNET - VOI2013 8 năm trước
|
(+0)
|
Mình cũng vừa nhận ra... giới hạn m những 10^6. Đpt ở trường hợp xấu hơi bị lớn. Dù sao cũng cảm ơn.
Mà cho mình hỏi luôn là hai cái cluster trên spoj khác gì nhau và cách đọc các thông số Mhz, Ghz,... giả sử như cluster của bài này là 3Ghz, tức là sẽ thực hiện được khoảng bao nhiêu phép tính trên giây?
|
|
|
Đã lưu IP
|
|
Đã khóa chức năng gửi bài. |
|