其实我觉得这种题目风格很像今天省选第三轮D1T1
都是在一个算法模型上去探索规律；
首先我们要做一遍最大流毫无疑问
第一问看起来很好想，只要是满流边就可以了？
错，反例不难找到
如：1--->2 flow 4
2--->3 flow 4
3--->1 flow 4
1--->4 flow 4
很有可能我们在找增广路的时候，走了多余的回路（1-2-3-1），导致前3条边也是满流边，但不会出现在最小割方案中
所以我们考虑用tarjan对残留网络缩点；
对于第一问，要求是满流边且起点终点在不同集合
第二问，显然在满足第一问的前提下，起点终点分属源点汇点集合
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.