bài HIWAY

Tiêu đề: bài HIWAY 15.01.09 22:54

vn.spoj.pl/problems/HIWAY
bài này yêu cầu tìm 2 đường đi ngắn nhất trên đơn đồ thị vô hướng.
Giải thuật
-tìm đường đi thứ 1 bằng Dijkstra, sau đó, ta xoá mỗi cạnh trên đường đi này và thêm vào các cung từ d[i+1] tới d[i] với trọng số bằng số đối trọng số bạn đầu (d[i] và d[i+1] là 2 đỉnh liên tiếp trên đường đi ngắn nhất khi truy vết bằng Dijkstra.
-tìm dg đi thứ 2 bằng Ford-Bellman (có thể chứng minh chính xác dc là kô có chu trình âm)
-output kết qủa.
Em bị WA, kô hiểu vì sao, help silent

Code:: #include <stdio.h>
//#include <fstream.h>
#define size 110
#define inf 999999999
int N,M,s,f;
int t[size][size];
int stdjk[size],stfb[size];
int t1,t2;
int Dijkstra();
int FordBellman();
main()
{
//ifstream fin("input.txt");
int i,j;
scanf("%d %d",&N,&M);
scanf("%d %d",&s,&f);
//fin>>N>>M>>s>>f;
//init graph
for (i=1;i<=N;++i)
{
for (j=1;j<=N;++j)
{
t[i][j]=inf;
}
t[i][i]=0;
}
//input graph
for (i=1;i<=M;++i)
{
int u,v,l;
scanf("%d %d %d",&u,&v,&l);
//fin>>u>>v>>l;
t[u][v]=t[v][u]=l;
}
//solve
int ld,lf;
if (s==f){}
else
{
ld=Dijkstra();
if (ld==-1) printf("-1\n");
else
{
lf=FordBellman();
if (lf==-1) printf("-1\n");
else
{
printf("%d\n",lf+ld);
printf("%d ",t1);
while (1)
{
printf("%d ",stdjk[t1--]);
if (t1==0)
{
printf("\n");
break;
}
}
printf("%d ",t2);
while (1)
{
printf("%d ",stfb[t2--]);
if (t2==0)
{
printf("\n");
break;
}
}
}
}
}
return 0;
}
int Dijkstra()
{
int fr[size],tr[size],la[size];
int i,u,m;
for (i=1;i<=N;++i)
{
fr[i]=0;
la[i]=inf;
}
la[s]=0;
do
{
u=0;m=inf;
for (i=1;i<=N;++i)
{
if (fr[i]==0&&la[i]<m)
{
m=la[i];
u=i;
}
}
if (u==0||u==f) break;
fr[u]=1;
for (i=1;i<=N;++i)
{
if (la[i]>la[u]+t[u][i])
{
la[i]=la[u]+t[u][i];
tr[i]=u;
}
}
} while (1);
//trace route
if (u==0) return -1;
else
{
t1=0;//init empty stack - stdjk
int len=0;
do
{
++t1;
stdjk[t1]=u;//push u
len+=t[tr[u]][u];//increase len
t[tr[u]][u]=inf;//delete edge from tr[u] to u
t[u][tr[u]]=-t[u][tr[u]];//insert a negative arc from u to tr[u]
u=tr[u];//trace u
if (u==s)
{
//push s and break
++t1;
stdjk[t1]=s;
break;
}
} while (1);
return len;
}
}
int FordBellman()
{
int la[size],tr[size];
int u,v,CountLoop,i,stop;
for (i=1;i<=N;++i)
la[i]=inf;
la[s]=0;
for (CountLoop=1;CountLoop<=N-1;++CountLoop)
{
stop=1;
for (u=1;u<=N;++u)
{
for (v=1;v<=N;++v)
{
if (la[v]>la[u]+t[u][v])
{
la[v]=la[u]+t[u][v];
tr[v]=u;
stop=0;
}
}
}
if (stop==1) break;
}
//trace route
if (la[f]==inf) return -1;
else
{
t2=0;//init empty stack - stfb
int len=0;
u=f;
do
{
++t2;
stfb[t2]=u;//push u
len+=t[tr[u]][u];//increase len
u=tr[u];//trace u
if (u==s)
{
//push s and break
++t2;
stfb[t2]=s;
break;
}
} while (1);
return len;
}
}

Tiêu đề: Re: bài HIWAY 17.01.09 11:43

Anh co the noi ro mot chut ve cach chung minh duoc khong

Tiêu đề: Re: bài HIWAY 17.01.09 15:04

Chứng minh kô có chu trình âm thế này.
Giả sử có một chu trình âm suy ra nó phải đi qua một số cung liên tiếp nhau trong những cung mà ta thêm vào suy khi truy vết từ Dijkstra (vì chỉ có những cung này mới có weight<0).
Do chu trình này âm suy ra giá trị tuyệt đối của tổng trọng số những cung âm phải lớn hơn tổng trọng số những cạnh kia, suy ra là có một đường đi ngắn hơn đường đi theo những cung âm ban đầu, điều này là vô lý.

Tiêu đề: Re: bài HIWAY 17.01.09 20:31

cam on su giup do
em lam theo ca 2 lan deu la forbellman
http://vn.spoj.pl/status/HIWAY,ktuan/

Tiêu đề: Re: bài HIWAY 17.01.09 23:43

Em có thể share source code được không.

Tiêu đề: Re: bài HIWAY 18.01.09 9:07

const
fileinp = '';
fileout = '';
max = 100;
maxd = maxlongint;
var
fi, fo: text;
c: array[1..max, 1..max] of longint;
d: array[1..max] of int64;
Pre: array[1..max] of integer;
Tr: array[1..max, 1..max] of boolean;
cost, n, m, s, t, k, count: int64;
Queue: array[0..max] of integer;
InQueue: array[0..max] of boolean;
First, Last: integer;

procedure NhapDl;
var
i, u, v, w: integer;
begin
assign(fi, fileinp); reset(fi);
assign(fo, fileout); rewrite(fo);
{ readln(fi, n, m, k, s, t);}
readln(fi, n, m);
readln(fi, s, t);
k := 2;
fillchar(c, sizeof(c), 0);
for i := 1 to m do
begin
readln(fi, u, v, w);
c[u, v] := w;
c[v, u] := w;
end;
end;

procedure CloseFile;
begin
close(fi); close(fo);
end;

procedure Ford_Bell_Man;
var
i, j: integer;
begin
for i := 1 to n do d[i] := maxd;
d[s] := 0;
fillchar(Pre, sizeof(Pre), 0);
fillchar(InQueue, sizeof(InQueue), false);
First := 0; Last := 0; Queue[0] := s; InQueue[s] := true;
Count := 1;
repeat
i := Queue[First]; First := (First + 1) mod max;
InQueue[i] := false;
Count := Count - 1;
for j := 1 to n do
if (c[i, j] <> 0) and (d[j] > d[i] + c[i, j]) then
begin
d[j] := d[i] + c[i, j];
Pre[j] := i;
if not InQueue[j] then
begin
Last := (Last + 1) mod max;
Queue[Last] := j; InQueue[j] := true;
Count := Count + 1;
end;
end;
until Count = 0;
end;

procedure IncWay;
var
u, v: integer;
begin
v := t;
repeat
u := Pre[v];
if Tr[v, u] then {cung (u, v) la cung nguoc}
begin
c[u, v] := - c[u, v];
c[v, u] := c[u, v];
Tr[v, u] := false;
end
else
begin
Tr[u, v] := true;
c[u, v] := 0;
c[v, u] := - c[v, u];
end;
v := u;
until v = s;
end;

procedure PrintWay(v: integer);
var
u: integer;
begin
count := count + 1;
if v = s then
begin
write(fo, count, ' ',s);
exit;
end;
for u := 1 to n do if Tr[u, v] then
begin
Tr[u, v] := false;
PrintWay(u);
write(fo,' ',v);
break;
end;
end;

procedure Xuli;
var
i: integer;
begin
fillchar(Tr, sizeof(Tr), false);
cost := 0;
for i := 1 to k do
begin
Ford_Bell_Man;
if d[t] = maxd then
begin
writeln(fo, -1);
CloseFile;
Exit;
end;
cost := cost + d[t];
IncWay;
end;
writeln(fo, cost);
for i := 1 to k do
begin
count := 0;
PrintWay(t);
writeln(fo);
end;
CloseFile;
end;

BEGIN
NhapDl;
XuLi;
END.

Tiêu đề: Re: bài HIWAY 18.01.09 20:34

Bài này sửa lại là AC luôn bài KWAY mà sao ktuan không làm đi

Tiêu đề: Re: bài HIWAY 18.01.09 20:37

cu tu tu ma lam khong can voi! Very Happy

Tiêu đề: Re: bài HIWAY 18.01.09 20:48

chinh xong roi!Anh co the coi ket qua