PID306 / 破坏石油运输系统问题
题目描述

某组织打算摧毁发烂稀国的石油运输系统。该系统可以看成一个运输网络,由许多结点和连接结点的管道组成。只有地点A生产石油,生产的石油通过管道运输到地点B,石油不能在中间点累积。管道是双向的,每条管道连接两个不同的结点,每两个结点之间只有一条管道连接。每条管道有一个抗压指数,当石油的流量超过这个数管道就会爆炸。A地生产石油的速度是很快的,但由于抗压指数的问题,能运到B的有一个上限。发烂稀国比较贪婪,他们采用了使他们获得最多石油的运输方案。某组织有一个特殊的物质,能使一条管道的抗压指数下降1。作为该组织的首席程序员,你的任务就是告诉领导,让那些管道的抗压指数下降,一定可以摧毁发烂稀国的石油运输网络。

输入格式

第1行包含四个整数n,m,s,t,表示有n个结点(编号为1,2,3,……,n),m条管道,s和t分别是A地和B地的编号。2<=n<=130, 0<=m<=n (n-1)/2, 1<= s,t <= n。

接下来m行,每行描述一条管道,包含3个整数i, j, c。i, j 分别为管道连接的2个结点。C为该条管道的抗压指数。1<=i, j<=n, 1<=c <=10000。

输出格式

第1行输出抗压指数减少1就爆炸的管道的条数k。

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

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论