破坏行动

输入文件：destroy.in

输出文件：destroy.out

题目描述：

恐怖组织伊阿德尔的首领本拉灯打算摧毁一个敌对势力的石油运输系统。这个石油运输系统可以看成一个运输网络，由许多的节点和连接节点的管道构成。只有地点A生产石油，而生产的石油则通过管道运输送到地点B，石油不能在中间节点积累。管道是双向的，每条管道连接两个不同的节点，而每两个节点间最多只有一条管道相连。每条管道都有一个抗压指数，当石油的流量超过这个数管道就会爆炸。A地生产石油的速度可以认为非常快，但是由于管道抗压指数的原因，能运到B的有一个上限。本拉灯知道敌对势力采用了某种方式使得他们能输送最多的石油，但他不知道这个具体的方案是什么。本拉灯有一种特殊的物质，可以让一条管道的抗压指数下降1。作为伊阿德尔卡首席恐怖程序员，你的任务就是告诉本拉灯，让哪些管道的抗压指数下降，一定可以使管道爆炸从而摧毁运输网络。

输入格式：

第一行包含四个整数N，M，S，T，表示有N个节点（编号为1，2，3，……N），M条管道，S T分别是AA地和B地的编号。2<=n<=130 0<=m<=n*(n-1)/2  1<=s,t<=n.

接下来M行每行描述一条管道，包含三个整数I J C。 I和J分别为管道的连接的两个节点，C为这条管道的抗压指数。1<=I,j<=n 1<=c<=10000.

输出格式：

第一行输出抗压指数减少1就必定爆炸的管道的条数K。

接下来有K行，每行输出一个整数P（1<=p<=M），说明第p条管道如果抗压指数减少1就必定爆炸。序号p按照管道输入的顺序，并按照p的升序输出。

输入样例：

4 4 1 4

2 4 100

1 2 1

3 1 100

4 3 1

输出样例：

2

2

Program Destroy_Mpq;

type data=record
       limit,flow:integer;
     end;

Const Maxn=130;

var
  n,m,s,t,answer:integer;
  v:array[1..Maxn] of integer;
  g:array[1..Maxn,1..Maxn] of data;
  queue:array[1..Maxn] of integer;
  e:array[1..Maxn*Maxn,1..2] of integer;

procedure init;
var
  i,x,y,z:integer;
begin
  readln(n,m,s,t);
  for i:=1 to m do
  begin
    readln(x,y,z);
    g[x,y].limit:=z;
    g[y,x].limit:=z;
    e[i,1]:=x;
    e[i,2]:=y;
  end;
end;

function Mins(a,b:integer):integer;
begin
  if a>b then exit(b) else exit(a);
end;

procedure MaxFlow;
var
  i,j,Min,head,last:integer;
begin
  while true do
  begin
    fillchar(v,sizeof(v),0);
    head:=1; last:=1;
    queue[1]:=s;
    v[s]:=s;
    repeat
      if head<=last then i:=queue[head] else break;
      for j:=1 to n do
        if v[j]=0 then
          if g[i,j].flow<g[i,j].limit then
          begin
            inc(last);
            queue[last]:=j;
            v[j]:=i;
          end else
          if g[j,i].flow>0 then
          begin
            inc(last);
            queue[last]:=j;
            v[j]:=-i;
          end;
      inc(head);
    until v[t]<>0;

    if v[t]=0 then break;

    Min:=Maxint;
    i:=t;
    while i<>s do
    begin
      if v[i]>0 then Min:=Mins(g[v[i],i].limit-g[v[i],i].flow,Min) else
                     Min:=Mins(g[i,abs(v[i])].flow,Min);
      i:=abs(v[i]);
    end;

    i:=t;
    while i<>s do
    begin
      if v[i]>0 then inc(g[v[i],i].flow,Min) else
                     dec(g[i,abs(v[i])].flow,Min);
      i:=abs(v[i]);
    end;
  end;
end;

procedure Calc;
var
  i,j,k:integer;
begin
  for i:=1 to n do
    for j:=1 to n do
      dec(g[i,j].limit,g[i,j].flow);

  for k:=1 to n do
    for i:=1 to n do
      for j:=1 to n do
        if (g[i,k].limit>0) and (g[k,j].limit>0) then
          g[i,j].limit:=1;

  for i:=1 to m do
  begin
    if (g[e[i,1],e[i,2]].limit<=0) or (g[e[i,2],e[i,1]].limit<=0) then
      inc(answer);
  end;
  writeln(answer);
  for i:=1 to m do
  begin
    if (g[e[i,1],e[i,2]].limit<=0) or (g[e[i,2],e[i,1]].limit<=0) then
      writeln(i);
  end;
end;

begin
assign(input,'destroy.in'); reset(input);
assign(output,'destroy.out'); rewrite(output);
  init;
  MaxFlow;
  Calc;
close(input); close(output);
end.