Drainage Ditches （HDU - 1532）（最大流）

题意：有m个点，n条管道，问从1到m最大能够同时通过的水量是多少？

题解：最大流模板题。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

typedef long long ll;

const int INF = 0x3ffffff;

const int maxn = 205;

int gra[maxn][maxn];

int flow[maxn];

int path[maxn];

int n,m;

int bfs(int s, int e)

{

    queue<int>q;

    int t;

    memset(path,-1,sizeof(path));

    memset(flow,0,sizeof(flow));

    path[s] = 0;

    flow[s] = INF;

    q.push(s);

    while(!q.empty()){

        t = q.front();

        q.pop();

        if(t == e) break;

        for(int i = 1; i <= m; i ++)

        {

            if(i != s && gra[t][i] && path[i] == -1)

            {

                flow[i] = flow[t] < gra[t][i] ? flow[t] : gra[t][i];

                path[i] = t;

                q.push(i);

            }

        }

    }

    if(path[e] == -1)

        return -1;

    else return flow[e];

}

int EK(int s, int e){

    int maxflow = 0;

    int pre, now, step;

    while((step = bfs(s,e))!= -1){

        maxflow += step;

        now = e;

        while(now != s){

            pre = path[now];

            gra[pre][now] -= step;

            gra[now][pre] += step;

            now = pre;

        }

    }

    return maxflow;

}

int main()

{

    int u,v,c;

    while(~scanf("%d%d",&n,&m)){

        memset(gra,0,sizeof(gra));

        for(int i = 1; i <= n; i ++)

        {

            scanf("%d %d %d", &u,&v,&c);

            gra[u][v] += c;

        }

        int ans = EK(1,m);

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

Drainage Ditches （HDU - 1532）（最大流）

最新文章

热门文章