|
|
|
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 9 năm, 7 tháng trước
|
(+0)
|
bai nay sao em de mang ma tran ke [1..1000,1..1000] thi dc 40 diem.con [1..10000,1..10000] thi 0 diem vay may anh.
may anh coi thu em bi sai cho nao ma chi dc 40 diem vay?
| Code: |
const fi='';
fo='';
var a:array[1..1000,1..1000]of longint;
tham:array[1..10000]of boolean;
q,cha,b:array[1..10000]of longint;
l, n,m,s,t,max:longint; co:boolean;
procedure nhap;
var f:text; i,u,v:longint;
begin
assign(f,fi);
reset(f);
readln(f,n,m,s,t);
for i:=1 to m do
begin
readln(f,u,v);
a[u,v]:=1;
end;
close(f);
end;
procedure bfs(s:longint);
var u,v,dau,cuoi:longint;
begin
dau:=1;
cuoi:=1;
q[dau]:=s;
repeat
u:=q[dau];
for v:=1 to n do
if (a[u,v]=1) and ( not tham[v]) then
begin
cuoi:=cuoi+1;
q[cuoi]:=v;
cha[v]:=u;
if v=t then
begin
co:=true;
exit;
end;
end;
dau:=dau+1;
until dau>cuoi;
end;
procedure timduong;
var i,k:integer;
begin
k:=cha[t];
i:=0;
repeat
inc(i);
b[i]:=k;
k:=cha[k];
until k=s;
l:=i;
end;
procedure xuli;
var i:longint;
begin
max:=0;
bfs(s);
timduong;
co:=false;
for i:=1 to l do
begin
fillchar(q,sizeof(q),0);
fillchar(tham,sizeof(tham),false);
tham[b[i]]:=true;
bfs(s);
if not co then max:=max+1
else
co:=false;
end;
end;
procedure xuat;
var f:text;
begin
assign(f,fo);
rewrite(f);
writeln(f,max);
close(f)
end;
begin
nhap;
xuli;
xuat;
end.
|
|
|
|
|
 Đã lưu IP
|
|
|
LiF.Typn
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 9 năm, 7 tháng trước
|
(+0)
|
vankiepsau95 viết:
QUOTE:
Bài này em BFS tìm đường đi từ s->t. Rồi lần lượt bỏ điểm đó đi, nếu có đường khác từ s->t k cần qua diểm đó thì là k xung yếu ngược lại là xung yếu.
| Code: | const fi='';//'STNODE.inp';
fo='';//'STNODE.out';
type ptr=^node;
node=record
v : longint;
next:ptr;
end;
var f1,f2 : text;
tr,thu,q : array[0..10000] of longint;
f,l,i,dem,kq,n,m,s,t,v,u : longint;
k : array[0..10000] of ptr;
inq :array[0..10000] of boolean;
p : ptr;
procedure tinh;
var w : longint; p:ptr;
BEGIN
w:=t;
while w<>s do
BEGIN
w:=tr[w];
if w<>s then
BEGIN
inc(dem);
thu[dem]:=w;
end;
end;
end;
procedure bfs(u : longint);
var p:ptr;
BEGIN
f:=1;
l:=1;
fillchar(inq,sizeof(inq),false);
inq[u]:=true;
// inq[k]:=true;
q[f]:=u;
repeat
v:=q[f]; inc(f);
p:=k[v];
while p<> nil do
if inq[p^.v]=false then
BEGIN
inc(l);
q[f]:=p^.v;
tr[p^.v]:=v;
inq[p^.v]:=true;
if p^.v=t then
BEGIN
tinh;
exit;
end;
p:=p^.next;
end
else p:=p^.next;
until f>l;
end;
function bfs2(u,o : longint): boolean;
var p:ptr; v: longint;
BEGIN
fillchar(q,sizeof(q),0);
bfs2:=true;
f:=1;
l:=1;
fillchar(inq,sizeof(inq),false);
inq[u]:=true;
inq[o]:=true;
q[f]:=u;
repeat
v:=q[f];
inc(f);
p:=k[v];
[code]while p<> nil do
if inq[p^.v]=false then
BEGIN
inc(l);
q[f]:=p^.v;
inq[p^.v]:=true;
if p^.v= t then |
BEGIN
bfs2:=false;
exit;
end;
p:=p^.next;
end
else p:=p^.next;
until f>l;
end;
[/code]
Chắc là bạn này không quen ptr, nhìn cái BFS đã sai trầm trọng rồi
| Code: | while p<> nil do
if inq[p^.v]=false then
BEGIN
inc(l);
q[f]:=p^.v;
inq[p^.v]:=true;
if p^.v= t then |
|
|
|
|
Đã lưu IP
|
|
|
Cầu trời mai đề dễ chịu với con
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 9 năm, 7 tháng trước
|
(+0)
|
|
ai coi giup em cai code voi.sao em dc co 40d ah.
|
|
|
|
Đã lưu IP
|
|
|
LiF.Typn
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 9 năm, 7 tháng trước
|
(+0)
|
|
Bạn bè mà chú ăn nói như vậy à. Biết sai rồi.
|
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 9 năm, 7 tháng trước
|
(+0)
|
|
Thế phải nói thế nào ạ????
|
|
|
|
Đã lưu IP
|
|
|
Cầu trời mai đề dễ chịu với con
|
|
|
Đã khóa chức năng gửi bài. |
vttc (Thành viên)
Đã biết code đệ quy
Bài viết: 6
 
|
|
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 9 năm, 7 tháng trước
|
(+1)
|
manh1208 viết:
QUOTE:
ai coi giup em cai code voi.sao em dc co 40d ah.
bạn làm ma trận kề nên được 40đ thôi, còn mảng [1..10000, 1..10000] to quá nên khi nộp bị 0. trên voj bộ nhớ được 250MB.
|
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 9 năm, 7 tháng trước
|
(+0)
|
|
ngoai ma tran ke thi minh chi bik cai danh sach ke.
minh cg bik cai kieu j nua ak.wen ten mat oy... cai j ma ...start ak
|
|
|
|
Đã lưu IP
|
|
|
LiF.Typn
|
|
|
Đã khóa chức năng gửi bài. |
Chicharito (Thành viên)
Biết code binary-indexed tree
Bài viết: 46
|
|
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 9 năm, 7 tháng trước
|
(+0)
|
|
Forward star ^^, nói chung đây không là 1 phương pháp biểu diễn mà chỉ là 1 phần của cách biểu diễn đồ thị = danh sách kề, mình thì mình thích con trỏ hơn, bạn có thể xem cách cài con trỏ của bài ở dưới( tất nhiên là lưu ý phần bị sai), với những bài giới hạn to như thế này thì nên cài danh sách kề bạn ạ ^^
|
|
|
|
Đã lưu IP
|
|
|
Chúng ta muốn hòa bình chứ không phải là cầu hòa, chúng ta không bao giờ chịu làm bàn cờ cho tính toán của các nước lớn - Trung tướng Nguyễn Chí Vịnh- Tổng tham mưu trưởng quân đội nhân dân Việt Nam
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 9 năm, 7 tháng trước
|
(+0)
|
|
danh sach ke thj kho khan viec kiem tra.hoi lau
|
|
|
|
Đã lưu IP
|
|
|
LiF.Typn
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: STNODE - Ai ACC được 100đ chỉ giáo giùm mình với! 9 năm, 7 tháng trước
|
(+0)
|
|
Bạn manh1208 nhớ gõ tiếng Việt có dấu trên diễn đàn.
|
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
Được ưa thích: 0
