EdmondsKarp

2009-03-30 17:03

#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];
void BFS(int s,int n);
int GetMinCf(int t);
int EdmondsKarp(int s,int t,int n);
int main(void){
    int n,e,s,t,a,b,ct;
    int i,j,Max;
    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;
    }
   
    Max = EdmondsKarp(s,t,n);
   
    out<<Max<<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 EdmondsKarp(int s,int t,int n){
    int i,j,aug,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;
    BFS(s,n);
    while(father[t]){
         aug = GetMinCf(t);
         flow += aug;
        
         for(i=t;i!=s;i=father[i]){
            f[father[i] ][i] += aug;
            f[i][father[i] ] = -f[father[i] ][i];
            cf[father[i] ][i] -= aug;
            cf[i][father[i] ] += aug;
         }
         
         BFS(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 BFS(int s,int n){
     int front,tail,q[MAX];//如果已知队中可能存在的最大元素数量，则不必使用链队列

     int i,u,v;
     bool vs[MAX];
    
     memset(vs,0,sizeof(vs) );
     memset(father,0,sizeof(father) );
     front = tail = 0;
     q[tail++] = s;
     while(front!=tail){
          u = q[front++];
          vs[u] = true;
          for(i=0;i<Edge[u].n;i++){
              v = Edge[u].adjvex[i];
              if(!vs[v]&&cf[u][v]>0){
                 q[tail++] = v;
                 father[v] = u;
              }
          }
     }
}