|
|
|
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước
|
(+1)
|
Hy vọng là các anh cố gắng làm 1 bản pdf solution giống PreVOI Hải Phòng cho mọi người tham khảo  Cám ơn các anh rất nhiều |
|
|
|
 Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước
|
(+0)
|
baolaptrinh viết:
QUOTE:
Bạn lấy abs(f[n]) đi vì nó có thể âm đó.Mình sửa đó và AC:D
Với bài của mình thì f[n] không thể âm dc do f[i]<= s[i] với mọi i
|
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước
|
(+0)
|
linuxpro viết:
QUOTE:
Với bài của mình thì f[n] không thể âm dc do f[i]<= s[i] với mọi i
Bạn share code mình xem thử sao!
|
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước
|
(+0)
|
khanhsuphu12 viết:
QUOTE:
Bài VOCACTUS mình dùng dijkstra để tìm đường đi vs time ngắn nhất từ s -> t. Nếu số đỉnh là lẻ -> exit và writefile. Nếu ko có đường đi thì exit -> -1. Nếu số đỉnh là chẵn thì loại bỏ từng đường đi trong đường đi ấy và tìm đường đi ngắn nhất từ s->t (lại kiểm tra nhưng những bước đã nói ở trên) :)
Và nếu không tìm được bằng các biện pháp trên thì exit -1
Bài VOCACTUS em làm theo ý tưởng này nhưng nộp lên chỉ được 5đ. Rất mong các anh chị chỉ dùm em chỗ sai để em sửa lại, em là coder mới mong được giúp đỡ 
| Code: | program VOCACTUS;
const fin='';
fon='';
type cung=record
v,w,link:longint;
end;
var d,trace,head:array[0..10000] of longint;
adj:array[0..10000] of cung;
avail:array[0..10000] of boolean;
n,m,s,f,dem,ts:longint;
procedure enter;
var i,u:longint;
begin
dem:=0;
fillchar(head,sizeof(head),0);
readln(n,m,s,f);
for i:=1 to m do
begin
inc(dem);
read(u,adj[dem].v,adj[dem].w);
adj[dem].link:=head[u];
head[u]:=dem;
inc(dem);
adj[dem].v:=u;
adj[dem].w:=adj[dem-1].w;
adj[dem].link:=head[adj[dem-1].v];
head[adj[dem-1].v]:=dem;
end;
dem:=1;
end;
procedure relax(u,v,w:longint);
begin
if d[v]>(d[u]+w) then
begin
d[v]:=d[u]+w;
trace[v]:=u;
end;
end;
procedure dijkstra;
var u,v,i:longint;
begin
repeat
u:=0;
for v:=1 to n do
if (avail[v]=true) and (d[v]<d[u]) then
u:=v;
if (u=0) or (u=f) then break;
avail[u]:=false;
i:=head[u];
while i<>0 do
begin
relax(u,adj[i].v,adj[i].w);
i:=adj[i].link;
end;
until false;
end;
procedure truyvet;
begin
if d[f]=10000000 then writeln(-1)
else
begin
ts:=d[f];
while f<>s do
begin
inc(dem);
f:=trace[f];
end;
end;
end;
procedure delete;
begin
d[f]:=0;
while f<>s do
begin
f:=trace[f];
d[f]:=0;
end;
end;
procedure solve;
var i:longint;
begin
for i:=0 to n do d[i]:=10000000;
d[s]:=0;
fillchar(avail[1],n*sizeof(avail[1]),true);
dijkstra;
truyvet;
if (dem mod 2 <> 0) then
begin
writeln(ts);
exit;
end
else
begin
delete;
fillchar(avail[1],n*sizeof(avail[1]),true);
dijkstra;
truyvet;
end;
writeln(-1)
end;
BEGIN
assign(input,fin);
reset(input);
assign(output,fon);
rewrite(output);
enter;
solve;
close(input);
close(output);
END.
|
|
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước
|
(+0)
|
HelloSirius viết:
QUOTE:
linuxpro viết:
QUOTE:
Với bài của mình thì f[n] không thể âm dc do f[i]<= s[i] với mọi i
Bạn share code mình xem thử sao! :D
Mình sửa được rồi . không phải lỗi đó, cũng không biết sai ở đâu nữa. Mình chỉ sửa lại cái cây cho giảm bộ nhớ đi thì AC
|
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước
|
(+0)
|
pe_nhok_su viết:
QUOTE:
khanhsuphu12 viết:
QUOTE:
Bài VOCACTUS mình dùng dijkstra để tìm đường đi vs time ngắn nhất từ s -> t. Nếu số đỉnh là lẻ -> exit và writefile. Nếu ko có đường đi thì exit -> -1. Nếu số đỉnh là chẵn thì loại bỏ từng đường đi trong đường đi ấy và tìm đường đi ngắn nhất từ s->t (lại kiểm tra nhưng những bước đã nói ở trên) :)
Và nếu không tìm được bằng các biện pháp trên thì exit -1
Bài VOCACTUS em làm theo ý tưởng này nhưng nộp lên chỉ được 5đ. Rất mong các anh chị chỉ dùm em chỗ sai để em sửa lại, em là coder mới mong được giúp đỡ :)
| Code: | program VOCACTUS;
const fin='';
fon='';
type cung=record
v,w,link:longint;
end;
var d,trace,head:array[0..10000] of longint;
adj:array[0..10000] of cung;
avail:array[0..10000] of boolean;
n,m,s,f,dem,ts:longint;
procedure enter;
var i,u:longint;
begin
dem:=0;
fillchar(head,sizeof(head),0);
readln(n,m,s,f);
for i:=1 to m do
begin
inc(dem);
read(u,adj[dem].v,adj[dem].w);
adj[dem].link:=head[u];
head[u]:=dem;
inc(dem);
adj[dem].v:=u;
adj[dem].w:=adj[dem-1].w;
adj[dem].link:=head[adj[dem-1].v];
head[adj[dem-1].v]:=dem;
end;
dem:=1;
end;
procedure relax(u,v,w:longint);
begin
if d[v]>(d[u]+w) then
begin
d[v]:=d[u]+w;
trace[v]:=u;
end;
end;
procedure dijkstra;
var u,v,i:longint;
begin
repeat
u:=0;
for v:=1 to n do
if (avail[v]=true) and (d[v]<d[u]) then
u:=v;
if (u=0) or (u=f) then break;
avail[u]:=false;
i:=head[u];
while i<>0 do
begin
relax(u,adj[i].v,adj[i].w);
i:=adj[i].link;
end;
until false;
end;
procedure truyvet;
begin
if d[f]=10000000 then writeln(-1)
else
begin
ts:=d[f];
while f<>s do
begin
inc(dem);
f:=trace[f];
end;
end;
end;
procedure delete;
begin
d[f]:=0;
while f<>s do
begin
f:=trace[f];
d[f]:=0;
end;
end;
procedure solve;
var i:longint;
begin
for i:=0 to n do d[i]:=10000000;
d[s]:=0;
fillchar(avail[1],n*sizeof(avail[1]),true);
dijkstra;
truyvet;
if (dem mod 2 <> 0) then
begin
writeln(ts);
exit;
end
else
begin
delete;
fillchar(avail[1],n*sizeof(avail[1]),true);
dijkstra;
truyvet;
end;
writeln(-1)
end;
BEGIN
assign(input,fin);
reset(input);
assign(output,fon);
rewrite(output);
enter;
solve;
close(input);
close(output);
END.
|
mình nghĩ có thể bị quá thời gian,giới hạn n đến 10^5 lận mà.. bài này bắt buộc phải cài heap thôi
|
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm trước
|
(+0)
|
vodanh9x viết:
QUOTE:
bài VOBOARD: gọi b[i] là số lượng lần nâng hàng i, c[i] là số lần nâng cột i
=> đk thỏa mãn là (b[i]+c[j]+a[i,j]) mod k = 0 vs mọi i=1..m,j=1..n;
lại thấy b[i],c[j]<K
từ đó for giá trị của b[1] (0->k-1) rồi tính các c[j],b[i] trong O(m+n) => đpt là K*(M+N) (70%) :D
:S
cái c[j],b[i] tính là mình tăng c[j] lên rồi lại tăng b[i] lên từng cái hay răng anh?
|
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm trước
|
(+0)
|
iamquang95 viết:
QUOTE:
| Code: | 6 8 1 6
1 2 1
2 5 1
5 6 1
1 5 20
1 6 10
2 3 1
3 4 1
4 2 1 |
hình như test này không phải là đồ thị xương rồng, có canh (1,2) và (2,5) thuộc 2 chu trinhg (1-2-5-1) và (1-2-5-6-1) đúng không?
|
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm trước
|
(+0)
|
Bài VOCACTUS mình AC với thuật toán như sau, vẫn chưa thấy ai đưa ra thuật toán này:
- Xác định các chu trình trong đồ thị, cạnh nào thuộc chu trình nào
- Duyệt bắt đầu từ S, xử lí chu trình đầu tiên chứa đỉnh S, cứ gặp 1 cạnh thuộc chu trình mới, ta xét chu trình bắt đầu từ đỉnh u được gặp đầu tiên đó.
Tại mỗi lần duyệt 1 chu trình: cập nhật đường đi ngắn nhất theo 2 chiều tương ứng với 2 cạnh nối với u trong chu trình, khi vẽ ra có thể hiểu là "chiều kim đồng hồ" và "ngược chiều kim đồng hồ" . Đường đi ngắn nhất gồm đường đi lẻ dl[v] và đường đi chẵn dc[v], trong đó:
dl[v]=min(dl[v], dc[p]+c[v, p])
dc[v]=min(dc[v], dl[p]+c[v, p])
Với p là đỉnh cha của v trong chiều đang xét.
Khi duyệt hết chu trình thì ta có đường đi cần tìm là dl[T] .
Tính đúng đắn: do các tính chất đặc biệt của đồ thị xương rồng . |
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
Được ưa thích: 1
