【codevs1993】草地排水

2014年1月26日2,3183

题目描述 Description

在农夫约翰的农场上,每逢下雨,Bessie最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了,并且小草要继续生长还要花相当长一段时间。因此,农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼(不用担心,雨水会流向附近的一条小溪)。作为一名一流的技师,农夫约翰已经在每条排水沟的一端安上了控制器,这样他可以控制流入排水沟的水流量。

农夫约翰知道每一条排水沟每分钟可以流过的水量,和排水系统的准确布局(起点为水潭而终点为小溪的一张网)。需要注意的是,有些时候从一处到另一处不只有一条排水沟。

根据这些信息,计算从水潭排水到小溪的最大流量。对于给出的每条排水沟,雨水只能沿着一个方向流动,注意可能会出现雨水环形流动的情形。

输入描述 Input Description

第1行: 两个用空格分开的整数N (0 <= N <= 200) 和 M (2 <= M <= 200)。N是农夫John已经挖好的排水沟的数量,M是排水沟交叉点的数量。交点1是水潭,交点M是小溪。

第二行到第N+1行: 每行有三个整数,Si, Ei, 和 Ci。Si 和 Ei (1 <= Si, Ei <= M) 指明排水沟两端的交点,雨水从Si 流向Ei。Ci (0 <= Ci <= 10,000,000)是这条排水沟的最大容量。

输出描述 Output Description

输出一个整数,即排水的最大流量。

样例输入 Sample Input

样例输出 Sample Output

50

代码

抄抄代码画画图就懂了

打了个边表的

 

  • De℃,.: )2016年1月17日 下午7:27 回复

    第二个的49行应该是h[x] = -1;吧?

    #1  
  • 夜末蓅-灵魂2016年11月23日 下午7:55 回复

    请问:if(!used)h ==-1;在第二份代码49行的里边儿没有作用吧

    #2  
    • hzwer2016年11月24日 上午10:40 回复
      admin

      写错了

      #21