CUGB图论专场2：E - Drainage Ditches 最大流EK算法与Dinic算法

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

50

这题比D题还容易，最大流水题……不过是很经典的题目，没有什么转化，全裸的最大流。

1.EK算法：有点像Dinic算法，因为这个是从Dinic算法中来的，把分层去掉了而已，所以代码在DFS中还是有点像的，正向边减和反向边加。

1是源点，m是汇点，直接用EK算法0ms过……因为怕结果超出int，所以结果用了long long 型。

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define MM 10002
#define MN 205
#define INF 168430090
using namespace std;
typedef long long ll;
int n,m,k,t,pre[MN],vis[MN],Map[MN][MN];
ll ans;
int bfs()
{
    mem(vis,0); queue<int>q; q.push(1); vis[1]=1;
    while(!q.empty())  //找增广路
    {
        int u=q.front(); q.pop();
        for(int v=1;v<=m;v++)
        {
            if(!vis[v]&&Map[u][v])
            {
                pre[v]=u;  //记录前向结点
                if(v==m) return 1;
                q.push(v); vis[v] = 1;
            }
        }
    }
    return 0;
}
void change()
{
    int i,sum=INF;
    for(i=m; i != 1; i = pre[i])
        sum = min(sum,Map[pre[i]][i]);
    for(i=m; i != 1; i = pre[i])
    {
        Map[pre[i]][i]-=sum; //正向边减
        Map[i][pre[i]]+=sum; //反向边加
    }
    ans+=sum;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        mem(Map,0); ans=0;
        int u,v,w,i;
        while(n--)
        {
            scanf("%d%d%d",&u,&v,&w);
            Map[u][v]+=w;
        }
        while(bfs()) change();
        pri(ans);
    }
    return 0;
}

2.Dinic算法：

学习此算法的博客网址：http://www.cnblogs.com/acSzz/archive/2012/09/13/2683820.html

在图论书中也有说明此算法的。简单来说就是分层，从源点开始从0一层一层往后推，然后大于汇点的层（包括点与边）在DFS中就没有用到了，就相当于把这些点与边去掉了，这样当然效率更高啦！！！这就是EK算法中不相同的地方，EK是Dinic简化而来的，但是效率不如Dinic好，因为未分层，所以查询了不必要的边与结点。

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define MM 10002
#define MN 205
#define INF 168430090
using namespace std;
typedef long long ll;
int n,m,d[MN],Map[MN][MN];
ll ans;
int bfs()
{
    mem(d,-1);
    queue<int>q; q.push(1); d[1]=0;
    while(!q.empty())  //找增广路
    {
        int u=q.front(); q.pop();
        for(int v=1;v<=m;v++)
        {
            if(d[v]==-1&&Map[u][v])
            {
                d[v]=d[u]+1; //分层，越往后，层数越大
                q.push(v);
            }
        }
    }
    return d[m]!=-1;
}
int dfs(int u,int Min)
{
    int sum;
    if(u==m) return Min;
    for(int v=1;v<=m;v++)
        if(Map[u][v]&&d[v]==d[u]+1&&(sum=dfs(v,min(Min,Map[u][v]))))
        {
            Map[u][v]-=sum;
            Map[v][u]+=sum;
            return sum;
        }
    return 0;
}
void Dinic()
{
    int tmp;
    while(bfs())
    {
        while(tmp=dfs(1,INF))
            ans+=tmp;
    }
    pri(ans);
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        mem(Map,0); ans=0;
        int u,v,w;
        while(n--)
        {
            scanf("%d%d%d",&u,&v,&w);
            Map[u][v]+=w;
        }
        Dinic();
    }
    return 0;
}

CUGB图论专场2：E - Drainage Ditches 最大流EK算法与Dinic算法

原文：http://blog.csdn.net/u011466175/article/details/19333117