游客 Signup | Login
中文 | En

2510 - 草地排水

通过次数

0

提交次数

0

Time Limit : 1 秒 Memory Limit : 128 MB

在农夫约翰的农场上，每逢下雨，贝茜最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名? 涣鞯募际Γ┓蛟己惨丫诿刻跖潘档囊欢税采狭丝刂破鳎庋梢钥刂屏魅肱潘档乃髁俊?FONT face="Times New Roman">

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

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

Input

输入包含多组数据

第1行: 两个用空格分开的整数N (0 <= N <= 200) 和 M (2 <= M <= 200)。N是农夫约翰已经挖好的排水沟的数量，M是排水沟交叉点的数量。交点1是水潭，交点M是小溪。
第二行到第N+1行: 每行有三个整数，Si, Ei, 和 Ci。Si 和 Ei (1 <= Si, Ei <= M) 指明排水沟两端的交点，雨水从Si 流向Ei。Ci (0 <= Ci <= 10,000,000)是这条排水沟的最大容量。

Output

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

Examples

Input Format

5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

Output Format

50

Solution C++

//#include<bits/stdc++.h>
#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
#define Max_v 210
#define INF 1<<30
using namespace std;
typedef struct edge
{
    int to,cap,rev;
};
vector<edge>G[Max_v];
bool used[Max_v];
void add_edge(int from,int to,int cap)
{
	edge k;
	k.to=to;k.cap=cap;k.rev=G[to].size();
    G[from].push_back(k);
	k.to=from;k.cap=0;k.rev=G[from].size()-1;
	G[to].push_back(k);
}
int dfs(int v,int t,int f)
{
    if (v==t) return f;
    used[v]=true;
    for (int i=0;i<G[v].size();i++)
    {
        edge &e =G[v][i];
        if (!used[e.to] && e.cap > 0)  //之前走过的路，必定会填满,也是防止走循环
        {
            int d=dfs(e.to,t,min(e.cap,f));
            if (d>0)
            {
                e.cap-=d;
                G[e.to][e.rev].cap+=d;    //反向边增长
                return d;
            }
        }
    }
    return 0;
}
int max_flow(int s,int t)
{
    int flow=0;
    while(1)
    {
        memset(used,0,sizeof(used));
        int f = dfs(s,t,INF);
        if (f==0) return flow;
        flow+=f;
    }
}
void init(void)
{
	for (int i=0;i<Max_v;i++)
		G[i].clear();
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
		init();
        while(n--)
        {
            int from,to,cap;
            scanf("%d%d%d",&from,&to,&cap);
            add_edge(from,to,cap);
        }
        printf("%d\n",max_flow(1,m));
    }
    return 0;
}
请先登陆