1994. [CF 343E]供水泵站

【题目描述】

疯狂科学家Mike找到了一份工作。他的任务是管理一套供水泵站系统。

系统由n个水泵组成，从1到n编号。一些水泵之间有无向管道连接，水可以在其中双向流动（但同一时刻只能流向一个方向）。你知道每条管道的容量——每小时内在其中流动的最大水量，单位为升。每个水泵可以经由水管向其他水泵泵水，或接受泵来的水。需要确保每小时内流进该水泵的总水量恰好等于流出该水泵的总水量。

Mike的职责是在水泵间泵水。从水泵a到水泵b，根据上述规则，每小时经由管道（可能经过其他水泵）能够输送一定数量的水。在这段时间内，水不能流入水泵a，也不能流出水泵b。但是可以从水泵a流出任意数量的水，也能有任意数量的水流入水泵b。如果一小时内总共有x升水流出a，Mike就将多获得x元薪水。

为了得到报酬，根据合同，Mike需要工作n-1天。第一天他选择两个水泵v1和v2，然后在一小时内从v1向v2输送一些水。之后，在第i天，他选择一个之前从未选择过的水泵vi+1，并从水泵vi向水泵vi+1输送一些水。第i天输送的水量和第i-1天的无关。

Mike需要赚取尽可能多的钱以进行他的项目。帮助Mike找到水泵编号的一个排列v1,v2,...,vn，使得Mike能获得尽可能多的薪水。

【输入格式】

第一行两个数n,m（2<=n<=200,1<=m<=1000），分别代表水泵和管道的数量。

接下来有m行，第i行有三个空格隔开的整数ai,bi,ci（1<=ai,bi<=n,ai≠bi,1<=ci<=100），分别代表该管道连接的两个水泵，以及管道的容量。假定任意两个水泵之间至多只有一条管道，而且任意两个水泵之间都有一条包含若干管道的路径相连。

【输出格式】

一行一个整数，即Mike能获得的最大钱数。

【样例输入】

6 11

1 2 10

1 6 8

2 3 4

2 5 2

2 6 3

3 4 5

3 5 4

3 6 2

4 5 7

4 6 2

5 6 3

【样例输出】

77

【提示】

方案之一为：6 2 1 5 3 4

和原题不同，这里并未要求输出方案。

【来源】

CODEFORCES 343E