啊哈磊_编程从这里起步

标题: Ford-Fulkerson算法 [打印本页]

作者: admin 时间: 2013-2-20 20:01
标题: Ford-Fulkerson算法
[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]

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

欢迎光临啊哈磊_编程从这里起步 (https://bbs.codeaha.com/)