DFS版的FordFulkerson

2009-03-30 17:04

#include<iostream>
#include<fstream>
using namespace std;

const int MAX = 100;

struct{
      int n;
      int adjvex[MAX];
}Edge[MAX];

int f[MAX][MAX],c[MAX][MAX],cf[MAX][MAX],father[MAX];
bool vs[MAX];

void DFS(int cur,int n);
int GetMinCf(int t);
int FordFulkerson(int s,int t,int n);

int main(void){
    int n,e,s,t,a,b,ct;
    int i,j;
    ifstream in("data.in");
    ofstream out("data.out");
   
    in>>n>>e>>s>>t;
    for(i=1;i<=n;i++)
        Edge[i].n = 0;
   
    memset(c,0,sizeof(c) );
    for(i=0;i<e;i++){
        in>>a>>b>>ct;
        Edge[a].adjvex[ Edge[a].n++ ] = b;
        c[a][b] = ct;
    }
   
    out<<FordFulkerson(s,t,n)<<endl;
    for(i=1;i<=n;i++)
       for(j=1;j<=n;j++)
          if(f[i][j])
            out<<"f["<<i<<"]["<<j<<"]="<<f[i][j]<<endl;
   
    system("pause");
    return 0;
}

int FordFulkerson(int s,int t,int n){
    int i,j,inc,flow;
    
    for(i=1;i<=n;i++)
       for(j=1;j<=n;j++){
           f[i][j] = 0;
           cf[i][j] = c[i][j]-f[i][j];
       }
   
    flow = 0;
    memset(father,0,sizeof(father) );
    memset(vs,0,sizeof(vs) );
    DFS(s,n);
    while(father[t]){
         inc = GetMinCf(t);
         flow += inc;
         
         for(i=t;i!=s;i=father[i]){
            f[father[i] ][i] += inc;
            f[i][father[i] ] = -f[father[i] ][i];
            cf[father[i] ][i] -= inc;
            cf[i][father[i] ] += inc;
         }
         
         memset(vs,0,sizeof(vs) );
         memset(father,0,sizeof(father) );
         DFS(s,n);
    }
   
    return flow;
}

int GetMinCf(int t){
    int r;
   
    r = cf[father[t] ][t];
    for(int i=father[t];father[i];i=father[i])
        if(cf[father[i] ][i]<r)
           r = cf[father[i] ][i];
          
    return r;
}

void DFS(int cur,int n){
     int i,v;
    
     vs[cur] = true;
     for(i=1;i<=n;i++)//注意此处流网络与一般有向图的区别(边的可反性)

        if(!vs[i]&&cf[cur][i]>0){
           father[i] = cur;
           DFS(i,n);
        }
}