HDU1532 Drainage Ditches （网络流）_其他编程jrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播_网络编程_码蚁之家_www.codes51.com jrs看球网直播吧_低调看直播体育app软件下载

HDU1532 Drainage Ditches （网络流）(2/2)

来源：互联网时间：2016/6/22 5:12:45

The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.

Output

For each case, output a single integer, the maximum rate at which water may emptied from the pond.

Sample Input

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

Sample Output

题意：n个点，m条单向边，求1到n的最大流。

分析：是一道网络流的基础入门题，也是道模板题。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int INF = 1e9;
const int MOD = 1e9+7;
#define ll long long
#define CL(a,b) memset(a,b,sizeof(a))
#define lson (i<<1)
#define rson ((i<<1)|1)
#define N 1010

int n,m,s,t;
int pre[N];
int mat[N][N];
bool vis[N];

bool bfs()
{
    int cur;
    queue Q;
    CL(pre, 0);
    CL(vis, false);
    vis[s] = true;
    Q.push(s);
    while(!Q.empty())
    {
        cur = Q.front();
        Q.pop();
        //cout<<>"<<>

上一页 1 2

明星图片