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

我记得capacity scaling是O(E^2lgC)的吧

Posted by frkstyc at 2006-06-27 23:27:58 on Problem 1459
In Reply To:您好, 我想了一下, 书上说最多进行log(f)次迭代,f是最终的最大流数值, 每次迭代O(e), 然后对比一下,和我以前的程序相比,常数应该说比较小,我也是用类似prim的贪心法找最大瓶颈路,指点一下吧 Posted by:semonteer at 2006-06-27 23:16:34

> 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:

要进行 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:

Home Page Go Back To top