Drainage Ditches---hdu1532（最大流）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1532

题意:

每次下雨的时候，农场主John的农场里就会形成一个池塘，这样就会淹没其中一小块土地，在这块土地上种植了Bessie最喜欢的苜蓿。这意味着苜蓿要被水淹没一段时间，而后要花很长时间才能重新长出来。因此，John修建了一套排水系统，这样种植了苜蓿的土地就不会被淹没。雨水被排到了附近的一条小河中。作为一个一流的工程师，John还在每条排水沟的起点安装了调节阀门，这样可以控制流入排水沟的水流的速度。

John不仅知道每条排水沟每分钟能排多少加仑的水，而且还知道整个排水系统的布局，池塘里的水通过这个排水系统排到排水沟，并最终排到小何中，构成一个复杂的排水网络。

给定排水系统，计算池塘能通过这个排水系统排水到小河中的最大水流速度。每条排水沟的流水方向是单方向的，但在排水系统中，流水可能构成循环。

求最大流模板；

有重边所以要累加

Dinic算法：

#include<stdio.h>

#include<string.h>

#include<queue>

#include<algorithm>

using namespace std;

#define N 220

#define INF 0xfffffff

int n, m, maps[N][N], d[N];

bool bfs(int s, int e)

{

    memset(d, , sizeof(d));

    queue<int>Q;

    int p;

    Q.push(s);

    d[s] = ;

    while(!Q.empty())

    {

        p=Q.front();Q.pop();

        if(p==e)

            return true;

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

        {

            if(maps[p][i] && !d[i])

            {

                d[i] = d[p] + ;

                Q.push(i);

            }

        }

    }

    return false;

}

int dfs(int u, int e, int Maxflow)

{

    int uflow=;

    if(u==e)

        return Maxflow;

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

    {

        if(maps[u][i] && d[i]==d[u]+)

        {

            int flow = min(maps[u][i], Maxflow-uflow);

            flow = dfs(i, e, flow);

            maps[u][i]-=flow;

            maps[i][u]+=flow;

            uflow += flow;

            if(uflow==Maxflow)break;

        }

    }

    if(uflow==)

        d[u]=;///减少循坏次数；

    return uflow;

}

int Dinic(int s, int e)

{

    int ans = ;

    while(bfs(s, e))

    {

        ans += dfs(s, e, INF);

    }

    return ans;

}

int main()

{

    int a, b, c;

    while(scanf("%d%d", &m, &n)!=EOF)

    {

        memset(maps, , sizeof(maps));

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

        {

            scanf("%d%d%d", &a, &b, &c);

            maps[a][b]+=c;

        }

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

    }

    return ;

}

EK算法：

#include<stdio.h>

#include<string.h>

#include<queue>

#include<algorithm>

using namespace std;

#define INF 0xfffffff

#define N 220

int maps[N][N], pre[N], ans;

bool bfs(int s, int e)

{

    memset(pre, , sizeof(pre));

    queue<int>Q;

    Q.push(s);

    while(Q.size())

    {

        int i = Q.front();

        Q.pop();

        if(i == e)

            return true;

        for(int j=; j<=e; j++)

        {

            if(pre[j]== && maps[i][j] > )

            {

                pre[j] = i;

                Q.push(j);

            }

        }

    }

    return false;

}

void EK(int s, int e)

{

    while(bfs(s, e))

    {

        int Min = INF;

        for(int i=e; i!=s; i=pre[i])

            Min=min(maps[pre[i]][i], Min);

         for(int i=e; i!=s; i=pre[i])

         {

             maps[pre[i]][i]-=Min;

             maps[i][pre[i]]+=Min;

         }

         ans+=Min;

    }

}

int main()

{

    int n, m, x, y,c;

    while(scanf("%d%d", &m, &n)!=EOF)

    {

        memset(maps, , sizeof(maps));

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

        {

            scanf("%d%d%d", &x, &y, &c);

            maps[x][y] += c;

        }

        ans = ;

        EK(, n);

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

    }

    return ;

}

巴特西

Drainage Ditches---hdu1532（最大流）

最新文章

热门文章