第一问不谈,
第二问首先我们要找出哪些是s到t的最短路上的边
由于是无向图,首先正反两遍最短路,求出是s到任意点的距离,任意点到t的距离(即t到任意点的距离);
然后穷举每条边判断是否在最短路上用d[x,y]表示x到y的最短路
则要满足d[s,x]+w(x,y)+d[y,t]=d[s,t],
然后以代价为流量建图跑最小割即可
注意每条无向边边要当做两条有向边考虑;
const inf=;
type node=record
from,point,next,flow:longint;
end; var edge:array[..] of node;
ans1,ans2:array[..] of longint;
p,cur,pre,numh,h,low,dfn,be,st:array[..] of longint;
tot,d,r,x,y,z,i,j,n,m,s,t,len:longint;
v,f:array[..] of boolean; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y,f:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].from:=x;
edge[len].flow:=f;
edge[len].next:=p[x];
p[x]:=len;
end; procedure sap;
var u,i,j,tmp,neck,q:longint;
begin
u:=s;
numh[]:=n;
while h[s]<n do
begin
if u=t then
begin
i:=s;
neck:=inf;
while i<>t do
begin
j:=cur[i];
if neck>edge[j].flow then
begin
neck:=edge[j].flow;
q:=i;
end;
i:=edge[j].point;
end;
i:=s;
while i<>t do
begin
j:=cur[i];
dec(edge[j].flow,neck);
inc(edge[j xor ].flow,neck);
i:=edge[j].point;
end;
u:=q;
end;
q:=-;
i:=p[u];
while i<>- do
begin
j:=edge[i].point;
if (edge[i].flow>) and (h[u]=h[j]+) then
begin
q:=i;
break;
end;
i:=edge[i].next;
end;
if q<>- then
begin
cur[u]:=q;
pre[j]:=u;
u:=j;
end
else begin
dec(numh[h[u]]);
if numh[h[u]]= then exit;
tmp:=n;
i:=p[u];
while i<>- do
begin
j:=edge[i].point;
if edge[i].flow> then tmp:=min(tmp,h[j]);
i:=edge[i].next;
end;
h[u]:=tmp+;
inc(numh[h[u]]);
if u<>s then u:=pre[u];
end;
end;
end; procedure tarjan(x:longint);
var i,y:longint;
begin
v[x]:=true;
f[x]:=true;
inc(r);
inc(d);
st[r]:=x;
dfn[x]:=d;
low[x]:=d;
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if edge[i].flow> then
begin
if not v[y] then
begin
tarjan(y);
low[x]:=min(low[x],low[y]);
end
else if f[y] then
low[x]:=min(low[x],low[y]);
end;
i:=edge[i].next;
end;
if low[x]=dfn[x] then
begin
inc(tot);
while st[r+]<>x do
begin
y:=st[r];
f[y]:=false;
be[y]:=tot;
dec(r);
end;
end;
end; begin
readln(n,m,s,t);
len:=-;
fillchar(p,sizeof(p),);
for i:= to m do
begin
readln(x,y,z);
add(x,y,z);
add(y,x,);
end;
sap;
for i:= to n do
if not v[i] then
begin
r:=;
d:=;
tarjan(i);
end;
i:=;
while i<=len do
begin
if (edge[i].flow=) then
begin
x:=edge[i].from;
y:=edge[i].point;
if be[x]<>be[y] then
begin
ans1[i div +]:=;
if (be[x]=be[s]) and (be[y]=be[t]) or (be[x]=be[t]) and (be[y]=be[s]) then
ans2[i div +]:=;
end;
end;
i:=i+;
end;
for i:= to m do
writeln(ans1[i],' ',ans2[i]);
end.