「NOIP模拟赛」花园的守护之神

2014年10月28日4,3693

题目描述

看着正在被上古神兽们摧残的花园,花园的守护之神――小Bug同学泪流满面。然而,FZOI不相信眼泪,小bug与神兽们的战争将进行到底!

通过google,小Bug得知,神兽们来自遥远的戈壁。为了扭转战局,小Bug决定拖延神兽增援的速度。从戈壁到达花园的路径错综复杂,由若干段双向的小路组成。神兽们通过每段小路都需要一段时间。小Bug可以通过向其中的一些小路投掷小xie来拖延神兽。她可以向任意小路投掷小Xie,而且可以在同一段小路上投掷多只小xie。每只小Xie可以拖延神兽一个单位的时间。即神兽通过整段路程的总时间,等于没有小xie时他们通过同样路径的时间加上路上经过的所有小路上的小xie数目总和。

神兽们是很聪明的。他们会在出发前侦查到每一段小路上的小Xie数目,然后选择总时间最短的路径。小Bug现在很想知道最少需要多少只小Xie,才能使得神兽从戈壁来到花园的时间变长。作为花园中可爱的花朵,你能帮助她吗?

输入格式

第1行包括一个整数N,表示地图中路点的个数;一个整数M,表示小路个数;以及整数S和T,分别表示戈壁和花园的路点编号。N个路点分别被编号为自然数1~N。

以下M行,每行三个整数A、B和C,表示路点A和B之间有一条小路相连,且通过它需要的时间为C。

输入数据保证两路点间最多只有一条小路相连,且戈壁和花园的路点是连通的。

输出格式

一个整数,表示使S到T之间最短路增长所需要的最少的小xie的数目。

输入样例

5 5 1 5

1 2 1

2 3 3

1 4 2

4 3 2

5 1

输出样例

1

数据范围

对于30%的数据,满足N≤10,M≤50。

对于50%的数据,满足N≤200,M≤10000。

对于全部的数据,满足N≤1000,M≤499500,0<C≤1000000。

题解

在最短路图中跑最大流(最小割)。。没了

 

avatar
1 Comment threads
2 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
小蒟蒻hzwer Recent comment authors
  Subscribe  
提醒
小蒟蒻

黄学长,请问输入样例最后一行为啥只有两个数啊?