随笔-68  评论-10  文章-0  trackbacks-0
/*
    sap+gap优化+当前弧优化, 采用邻接表+反向弧指针
    时间复杂度:O(mn^2)
*/



#include
<iostream>
using namespace std;

const int maxnode = 1024;
const int inf = 0x7fffffff;

struct edge
{
    
int ver;
    
int cap;       
    edge 
*next;   //next arc
    edge *rev;    //reverse arc
    edge() {}
    edge(
int Vertex, int Capacity, edge *Next):ver(Vertex), cap(Capacity), next(Next) {}
    
void* operator new(size_t, void* p) {return p;}
}
*Net[maxnode];

int dis[maxnode], num[maxnode], src, des, m, n;

int min(int a, int b)
{
    
return a<b? a:b;
}


void rev_bfs()
{
    
for(int i=1; i<=n; i++)
    
{
        dis[i] 
= maxnode;
        num[i] 
= 0;
    }


    
int q[maxnode], head = 0,tail = 0;
    q[tail
++= des;
    dis[des] 
= 0;
    num[
0= 1;
    
while(head != tail)
    
{
        
int v = q[head++];
        
for(edge *= Net[v]; e; e = e->next)
        
{
            
if(dis[e->ver] == maxnode && e->rev->cap > 0)
            
{
                dis[e
->ver] = dis[v] + 1;
                num[dis[e
->ver]]++;
                q[tail
++= e->ver;
            }

        }

    }

}


int maxflow()
{
    
int u, totalflow = 0;
    edge 
*curedge[maxnode], *revpath[maxnode];
    
for(int i=1; i<=n; i++) curedge[i] = Net[i];
    u 
= src;
    
while(dis[src] < n)
    
{
        edge 
*e;
        
for(e = curedge[u]; e; e = e->next)
            
if(e->cap > 0 && dis[u] == dis[e->ver] + 1break;
        
if(e)
        
{
            curedge[u] 
= e;
            revpath[e
->ver] = e->rev;
            u 
= e->ver;
            
if(u == des)
            
{
                
int augflow = inf, i;
                
for(i = src; i != des; i = curedge[i]->ver)
                    augflow 
= min(augflow, curedge[i]->cap);
                
for(i = src; i != des; i = curedge[i]->ver)
                
{
                    curedge[i]
->cap -= augflow;
                    curedge[i]
->rev->cap +=augflow;
                }

                totalflow 
+= augflow;
                u 
= src;
            }

        }

        
else
        
{
            
if(0 == (--num[dis[u]])) break;
            curedge[u] 
= Net[u];
            
int mindist = n;
            
for(edge *te = Net[u]; te; te = te->next)
                
if(te->cap > 0) mindist = min(mindist, dis[te->ver]);
            dis[u]
=mindist + 1;
            
++num[dis[u]];
            
if(u != src)
                u 
= revpath[u]->ver;
        }

    }

    
return totalflow;
}


int main()
{
    
int u, v, w;
    
while(scanf("%d%d"&m, &n) != EOF)
    
{
        edge 
*Te = new edge[2*m];
        edge 
*Pe = Te;
        src 
= 1;
        des 
= n;
        memset(Net,
0,sizeof(Net));
        
while(m--)
        
{
            scanf(
"%d%d%d"&u, &v, &w);
            
//if(u==v) continue;
            Net[u] = new((void*)Pe++) edge(v, w, Net[u]);
            Net[v] 
= new((void*)Pe++) edge(u, 0, Net[v]);
            Net[u]
->rev = Net[v];
            Net[v]
->rev = Net[u];
        }

        rev_bfs();
        printf(
"%d\n",maxflow());
        delete [] Te;
    }

    
return 0;
}
posted on 2011-05-10 13:17 wuxu 阅读(731) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理