Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

您好, 我想了一下, 书上说最多进行log(f)次迭代,f是最终的最大流数值, 每次迭代O(e), 然后对比一下,和我以前的程序相比,常数应该说比较小,我也是用类似prim的贪心法找最大瓶颈路,指点一下吧

Posted by semonteer at 2006-06-27 23:16:34 on Problem 1459
In Reply To:大O记号的意义你理解么？ Posted by:frkstyc at 2006-06-27 22:39:42

int EdmondsKarp(Graph C, Graph F,int S, int T, int nV){
    Graph R;
    for(int i = 0; i < nV; i++) for(int j = 0; j < nV; j++){
        R[i][j] = C[i][j];
        F[i][j] = 0;
    }    
    
    Path D,P,V;
    
    while(true){
      //  printf("AAAA\n");
        for(int i = 0; i < nV; i++) D[i] = -inf;
        for(int i = 0; i < nV; i++) V[i] = 0;
        D[S] = 0;
        for(int i = 0; i < nV; i++){
            int mx = -1;
            for(int j = 0; j < nV; j++){
                if(V[j]||D[j]==-inf) continue;
                if(mx==-1) mx = j;
                else if(D[j]>D[mx]) mx = j;
            }    
            if(mx==-1) break;
            V[mx] = 1;
            if(mx==T) break;
            for(int j = 0; j < nV; j++){
                if(V[j]||R[mx][j]<=0) continue;
                if(R[mx][j]>D[j]){
                    P[j] = mx;
                    D[j] = R[mx][j];
                }    
            }    
        }    
        if(!V[T]) break;
        int u,v,r = inf;
        for(v = T; v != S; v = P[v]){
            r <?= R[P[v]][v];
        }    
        for(v = T; v != S; v = P[v]){
            R[P[v]][v] -= r;        F[P[v]][v] += r;
            R[v][P[v]] += r;        F[v][P[v]] -= r;
        }    
    }    
    
    int Flow = 0;
    for(int i = 0; i < nV; i++) Flow += F[S][i];
    return Flow;
    
}

Followed by:

我记得capacity scaling是O(E^2lgC)的吧 (1491) frkstyc 2006-06-27 23:27:58
- 要进行 e*log(c) 次迭代? (0) semonteer 2006-06-27 23:31:26
- sorry 我错了 (0) semonteer 2006-06-28 00:01:50
  - 为什么这么菜... (0) semonteer 2006-06-28 00:02:06

Post your reply here:

User ID:
Password:
Title:

Content:

> int EdmondsKarp(Graph C, Graph F,int S, int T, int nV){
>     Graph R;
>     for(int i = 0; i < nV; i++) for(int j = 0; j < nV; j++){
>         R[i][j] = C[i][j];
>         F[i][j] = 0;
>     }    
>     
>     Path D,P,V;
>     
>     while(true){
>       //  printf("AAAA\n");
>         for(int i = 0; i < nV; i++) D[i] = -inf;
>         for(int i = 0; i < nV; i++) V[i] = 0;
>         D[S] = 0;
>         for(int i = 0; i < nV; i++){
>             int mx = -1;
>             for(int j = 0; j < nV; j++){
>                 if(V[j]||D[j]==-inf) continue;
>                 if(mx==-1) mx = j;
>                 else if(D[j]>D[mx]) mx = j;
>             }    
>             if(mx==-1) break;
>             V[mx] = 1;
>             if(mx==T) break;
>             for(int j = 0; j < nV; j++){
>                 if(V[j]||R[mx][j]<=0) continue;
>                 if(R[mx][j]>D[j]){
>                     P[j] = mx;
>                     D[j] = R[mx][j];
>                 }    
>             }    
>         }    
>         if(!V[T]) break;
>         int u,v,r = inf;
>         for(v = T; v != S; v = P[v]){
>             r <?= R[P[v]][v];
>         }    
>         for(v = T; v != S; v = P[v]){
>             R[P[v]][v] -= r;        F[P[v]][v] += r;
>             R[v][P[v]] += r;        F[v][P[v]] -= r;
>         }    
>     }    
>     
>     int Flow = 0;
>     for(int i = 0; i < nV; i++) Flow += F[S][i];
>     return Flow;
>     
> }

Home Page Go Back To top

您好, 我想了一下, 书上说 最多进行log(f)次迭代,f是最终的最大流数值, 每次迭代O(e), 然后对比一下,和我以前的程序相比,常数应该说比较小,我也是用类似prim的贪心法找最大瓶颈路,指点一下吧

您好, 我想了一下, 书上说最多进行log(f)次迭代,f是最终的最大流数值, 每次迭代O(e), 然后对比一下,和我以前的程序相比,常数应该说比较小,我也是用类似prim的贪心法找最大瓶颈路,指点一下吧