HDU1532 Drainage Ditches

                                                              Drainage Ditches

题目链接：Click Here~

题意解析：

    最近忙，好久没写了博客了。因为是第一次写网络流，所以写一下纪念一下。

    题意很简单，就是网络流中的最大流的定义。给出n条边，m个顶点。问你其中可以得到的最大流是多少。

算法分析：

    典型的最大流算法。我用的是EdmonsKarp算法，先用一个简单的。虽然，另外两个也学了。要注意检查一个点是否重复进入队列,还有就是因为改题的流量存在着0，所以，不能用流量是否为0来判断。一开始我一直错，后来才发现的，所以，我另设了一个变量。具体过程自己看代码吧。还有要注意重边的处理。其他的就是模板的事情了。

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

class EdmondsKarp{
   public:
      static const int N = 200+5;
      static const int INF = 1e8;
      int n,m,f,a[N],p[N],cap[N][N],flow[N][N];
      void Init(int n,int m){
          f = 0;
          this->n = n;
          this->m = m;
          memset(cap,0,sizeof(cap));
          memset(flow,0,sizeof(flow));
      }
      void AddEdge(int u,int v,int w);
      void Edmondskarp(int s,int t);
};
void EdmondsKarp::AddEdge(int u,int v,int w)
{
    cap[u][v] += w;                 //注意重边
}
void EdmondsKarp::Edmondskarp(int s,int t)
{
     queue<int> q;
     while(1){
         memset(a,0,sizeof(a));
         memset(p,-1,sizeof(p));     //注意破栈
         a[s] = INF;
         q.push(s);
         while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int v = 1;v <= m;++v){
              if(!a[v]&&p[v]==-1&&cap[u][v]>flow[u][v]){
                  p[v] = u;
                  q.push(v);
                  a[v] = min(a[u],(cap[u][v]-flow[u][v]));
              }
            }
         }
         if(a[t]==0)
            break;
         for(int u = t;u != s;u = p[u]){
            flow[p[u]][u] += a[t];
            flow[u][p[u]] -= a[t];
         }
         f += a[t];
     }
     printf("%d\n",f);
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        EdmondsKarp edmonds;
        edmonds.Init(n,m);
        int u,v,w;
        for(int i = 0;i < n;++i){
           scanf("%d%d%d",&u,&v,&w);
           edmonds.AddEdge(u,v,w);
        }
        edmonds.Edmondskarp(1,m);
    }
    return 0;
}

HDU1532 Drainage Ditches,布布扣,bubuko.com

HDU1532 Drainage Ditches

原文：http://blog.csdn.net/zhongshijunacm/article/details/21404089