Ford-Fulkerson算法

admin

[code=Cpp width=700px]/*
ID:huhu1711
LANG:C++
TASK:ditch
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<deque>
#include<cstring>
using namespace std;
int flag;
int E[201][201];
bool book[201];
deque <int> st;
int m,n;
void PrepareForDfs()
{
        flag=0;
        memset(book,0,sizeof(book));
        st.clear();
        st.push_back(n);
        book[n]=true;
}
void Dfs()
{
        int cur=st.back();
        if(cur==1)
                flag=1;
        if(flag==1)
                return;
        for(int i=1;i<=n;i++)
                if(E[cur]>0 && book==false)
                {
                        book=true;
                        st.push_back(i);
                        Dfs();
                        if(flag==1)
                                return;
                        st.pop_back();
                }
}
int main()
{
        freopen("ditch.in","r",stdin);
        freopen("ditch.out","w",stdout);
        cin >> m >> n;
        for(int i=1;i<=m;i++)
        {
                int x,y,z;
                cin >> x >> y >> z;
                E[y][x]+=z;
        }
        int ans=0;
        for(;;)
        {
                /*for(int i=1;i<=4;i++)
                {
                        for(int j=1;j<=4;j++)
                                cout << E[j] << ' ';
                        cout << endl;
                }*/
                PrepareForDfs();
                Dfs();
                if(flag==0)
                        break;
                int first,second;
                second=st.front();
                int start=second;
                st.pop_front();
                st.push_back(second);
                //cout << second << ' ';
                int min=2100000000;
                while(st.front()!=start)
                {
                        first=second;
                        second=st.front();
                        //cout << second << ' ';
                        st.pop_front();
                        st.push_back(second);
                        if(E[first][second] < min)
                                min=E[first][second];
                }
                ans+=min;
                second=st.front();
                //cout << endl << ans << endl << endl;
                st.pop_front();
                while(!st.empty())
                {
                        first=second;
                        second=st.front();
                        st.pop_front();
                        E[first][second]-=min;
                        E[second][first]+=min;
                }
        }
        cout << ans << endl;
        return 0;
}[/code]

复杂版:
有流量上下界的最大流最小流算法实现