Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
Trả lời: COMNET - VOI2013 (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
CHỦ ĐỀ - Trả lời: COMNET - VOI2013
#70294
leanhminh.cqb (Thành viên)
Đã biết code đệ quy
Bài viết: 5
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70297
dyn (Thành viên)
dyn-
Biết code binary-indexed tree
Bài viết: 37
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: COMNET - VOI2013 8 năm trước   (+0)
Mình nghĩ cách của bạn bị quá thời gian
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70300
leanhminh.cqb (Thành viên)
Đã biết code đệ quy
Bài viết: 5
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS