CUGBツーリズム専用フィールド2:E-Drainage Ditch最大ストリームEKアルゴリズムとDinicアルゴリズム

E- Drainage Ditch
Time Limit:1000 MS     メモリLimit:100000 KB     64 bit IO Format:%I 64 d&%I 64 u
Submit 
Status
Description
Every time itライヴFarmer John's fields,a pond forms over Bessie's favorite clover patch.This means that the clover is covered by water for awhile and tars quite a long time to regrow.Thus,Farmer Johter hatch ofthe water is drained to a nearby stream.Beng an ace engineer,Farmer John has also installed reglators the begining of each ditch,so he can control at rate water flowers intoth ditch. 
Farmer John knows not only how many gallows of water each ditch can transport per minute but also the exact layout of the ditch、which feed out of the pond and into each other and stream stream a potentallycomple.extwork. 
Given all this information、determine the maximure rate at which water can be transported out of the pond and into the strem.For any given ditch、water flows in in only one direct、but there might be a wathat carcarch.frect 
Input
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 ditch Farmer Johhhas dug.M isthenumber of intertititistininininstststininininstininininininininststststinininininininininininininininststststststs.s.s.ininininininininininininininininininininininininininininininininininininininininininininininininstststststststtains three integers,Si,Ei,and Ci.Si and Ei(1<=Si,Ei<=M)designate the intersections between which ditch ftch.Water will frowh this ditch ftch Si to Ei.Ci(0==Ci<=10,000,000,000)is the maximuthite
Output
For ach case、output a single integer、the maximrate at which water may empied from the pond.
Sample Input

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

Sample Output

50

この問題はD問題よりも易しいです.最大流水問題です.ただ経典的な問題です.転化は何もなくて、全裸の一番大きな流れです.
1.EKアルゴリズム:Dinicアルゴリズムに似ています.これはDinicアルゴリズムから来たもので、階層を取り除いただけです.だから、コードはDFSにまだ似ています.正方向にマイナスし、逆方向にプラスします.
1はソースで、mはシンクポイントで、直接EKアルゴリズムを0 msで通過します.結果が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
",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層を1層ずつ後ろに押して、それから送金ポイントより大きい層(点と辺を含む)は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
",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;
}