【GDOI2004】破坏行动

【GDOI2004】破坏行动

暂无测试数据。

Description

破坏行动(destroy.pas/c/cpp

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

Input

第一行包含四个整数n m s t ,表示有n个节点(编号为1,2,…,n), m 条管道,s t 分别是A地和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。

Output

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

Sample Input

4 4 1 4
2 4 100
1 2 1
3 1 100
4 3 1

Sample Output

2
2
4

Source

GDOI2004

信息

ID
1055
难度
(无)
分类
(无)
标签
(无)
递交数
0
已通过
0
通过率
?
上传者