posts - 274,  comments - 1258,  trackbacks - 0

 

#include < cstring >
// 常量定义:
const   int  maxV = 100 ;
const   double  Inf = 1e100;
// const int Inf=2000000000;
// Graph类定义:
template < class  T >
struct  GraphMatrix {
    
int  v;     // 顶点数
     int  e;     // 边数
    T a[maxV][maxV];     // 邻接矩阵
     void  init() {
        memset(a,
0 , sizeof (a));
    }

    
void  clear() {
        
int  i,j;
        
for (i = 0 ; i < v;  ++ i) {
            
for (j = 0 ; j < v;  ++ j)
                a[i][j]
= Inf;
        }

    }

}
;

#include
< list >
using  std::list;
template
< class  T >
struct  GraphList {
    
int  v;
    
int  e;
    list
< T >  a[maxV];     // 邻接表
     void  clear() { // clear()应在更改v之前进行
         int  i;
        
for (i = 0 ; i < v; i ++ )
            a[i].clear();
    }

    
~ GraphList() {
        v
= maxV;
        clear();
    }

}
;

namespace  bridgeNS {
/* 解决:查找、打印桥
 *算法:DFS——O(E)
 *输入:连通图(表):g
 *输出:屏幕
 
*/

    GraphList
< int >  g;
    
int  cnt;
    
int  pre[maxV];     // DFS顺序
     int  low[maxV];     // 最低前序编号:儿子low值的最小值
     void  _bridge( int  prnt,  int  w) {
        
int  v; // son
        low[w] = pre[w] = cnt ++ ;
        std::list
< int > ::iterator li;
        
for (li = g.a[w].begin(); li != g.a[w].end();  ++ li) {
            v
=* li;
            
if (pre[v] ==- 1 ) {
                _bridge(w,v);
                
if (low[w]  >  low[v]) low[w]  =  low[v];
                
if (low[v]  ==  pre[v])
                    printf(
" %d-%d\n " ,w,v); // 找到桥
            }
else   if (v != prnt  &&  low[w]  >  pre[v]) low[w]  =  pre[v];
        }

    }

    
void  bridge() {
        cnt
= 0 ;
        memset(pre,
- 1 , sizeof (pre));
        _bridge(
- 1 , 0 );
    }

}
        

namespace  GabowNS {
/* 解决:强分量
 *算法:Gabow——O(E)
 *输入:图(表):g
 *输出:分量编号sc[]
 
*/

    GraphList
< int >  g;
    
int  cnt0, cnt1;
    
int  sc[maxV]; // 分量编号
     int  pre[maxV];     // DFS顺序
     int  path[maxV],pp; // path栈
     int  stack[maxV],sp; //

    
void  _SCdfsR( int  w) {
        pre[w]
= cnt0 ++ ;
        stack[sp
++ ] = w;
        path[pp
++ ] = w;
        
int  v; std::list < int > ::iterator li;
        
for (li = g.a[w].begin(); li != g.a[w].end();  ++ li) {
            v
=* li;
            
if (pre[v] ==- 1 ) _SCdfsR(v);
            
else   if (sc[v] ==- 1 ) {
                
while (pre[path[pp - 1 ]]  >  pre[v])  -- pp;
            }

        }

        
if (path[pp - 1 !=  w)  return ;
        
-- pp;
        
do {
            sc[stack[
-- sp]] = cnt1;
        }
while (stack[sp]  !=  w);
        
++ cnt1;
    }

    
void  init() {
        memset(pre,
- 1 , sizeof (pre));
        memset(sc,
- 1 , sizeof (sc));
        cnt0
= cnt1 = 0 ;
        sp
= pp = 0 ;
        
int  i;
        
for (i = 0 ; i < g.v;  ++ i) {
            
if (sc[i] ==- 1 )
                _SCdfsR(i);
        }

    }


    
bool  isStrongReach( int  s,  int  t) {
        
return  sc[s] == sc[t];
    }

}


namespace  PrimNS {
/* 解决:最小生成树MST
 *算法:Prim——O(V^2)
 *输入:加权连通图(矩阵):g
 *输出:父节点st[],与其父之边的权重wt[]
 
*/

    GraphMatrix
< double >  g;
    
int  st[maxV];     // MST节点之父——用以保存MST
     double  wt[maxV + 1 ];     // 与其父的边的权重
     int  fr[maxV];     // 非树顶点的最近树顶点
     void  mst() {
        
int  v, w, min;
        
for (v = 0 ; v < g.v;  ++ v) {
            st[v]
=- 1 ; fr[v] = v; wt[v] = Inf;
        }

        st[
0 ] = 0 ; wt[g.v] = Inf;
        
for (min = 0 ; min != g.v;) {
            v
= min; st[v] = fr[v];
            
for (w = 0 , min = g.v; w < g.v;  ++ w) {
                
if (st[w] ==- 1 ) {
                    
if (g.a[v][w]  <  wt[w])
                        wt[w]
= g.a[v][w], fr[w] = v;
                    
if (wt[w]  <  wt[min])
                        min
= w;
                }

            }

        }

    }

}

    
namespace  DijkstraNS {  
/* 解决:非负权图单源最短路径树SPT
 *算法:Dijkstra——O(V^2)
 *输入:加权连通图(矩阵):g
 *输出:父节点st[],与其父之边的权重wt[]
 
*/

    GraphMatrix
< double >  g;
    
int  st[maxV];    
    
double  wt[maxV + 1 ];    
    
int  fr[maxV];     // 非树顶点的最近树顶点
     void  spt( int  s) {
        
int  v, w, min;
        
for (v = 0 ; v < g.v;  ++ v) {
            st[v]
=- 1 ; fr[v] = v; wt[v] = Inf;
        }

        st[s]
= s; wt[g.v] = Inf; wt[s] = 0 ;
        
for (min = s; min != g.v;) {
            v
= min; st[v] = fr[v];
            
for (w = 0 , min = g.v; w < g.v;  ++ w) {
                
if (st[w] ==- 1 ) {
                    
if (g.a[v][w] != Inf  &&  wt[v] + g.a[v][w]  <  wt[w])
                        wt[w]
= wt[v] + g.a[v][w], fr[w] = v;
                    
if (wt[w]  <  wt[min])
                        min
= w;
                }

            }

        }

    }

}

/**/
namespace  FloydNS { //   
/* 解决:所有点对最短路径
 *算法:Floyd——O(V^3)
 *输入:加权连通图(矩阵):g
 *输出:最短距离长度矩阵d[][], 路径矩阵p[][]
 
*/

    GraphMatrix
< double >  g;
    
double  d[maxV][maxV];     // 最短路径长度
     int  p[maxV][maxV];         // 最短路径下一顶点
     void  floyd() {
        
int  i,s,t;
        
for (s = 0 ; s < g.v;  ++ s) {
            
for (t = 0 ; t < g.v;  ++ t)
                
if ( (d[s][t]  =  g.a[s][t])  <  Inf)
                    p[s][t]
= t;
            d[s][s]
= 0 ;
        }

        
for (i = 0 ; i < g.v;  ++ i)
            
for (s = 0 ; s < g.v;  ++ s)
                
if (s != &&  d[s][i]  <  Inf)
                    
for (t = 0 ; t < g.v;  ++ t)
                        
if (d[s][t]  >  d[s][i]  +  d[i][t]) {
                            d[s][t] 
=  d[s][i]  +  d[i][t];
                            p[s][t] 
=  p[s][i];
                        }

    }

}

namespace  TenshiNS { //
/* 解决:二分图最大匹配
 *算法:匈牙利匹配(by Tenshi)——O(xv * yv)
 *输入:邻接矩阵g
 *输出:匹配数cnt,x匹配项xm[],y匹配项ym[]
 *备注:from Bug 06-07-07
 
*/

    
int  xv,yv;     // 顶点数
     int  g[maxV][maxV];     // g[i][j]=1 表示 xi与yj相邻
     int  sy[maxV];     // 辅助:当轮被搜过的y点都是1 
     int  cnt,xm[maxV],ym[maxV];  // 输出 
     void  init() {
        cnt
= 0 ;
        memset(g,
0 , sizeof (g));
        memset(xm,
- 1 , sizeof (xm));
        memset(ym,
- 1 , sizeof (ym));
    }

    
bool  _path( int  u) // 返回是否找到增广路
     {
        
for ( int  v = 0 ;v < yv;v ++ if (g[u][v]  &&   ! sy[v]) { sy[v] = 1 ;
            
if (ym[v] ==- 1   ||  _path(ym[v]))  { xm[u] = v; ym[v] = u;  return   1 ;}
        }
  return   0 ;    
    }

    
void  tenshi()
    
{
        
int  i;
        
for (i = 0 ;i < xv;i ++ )
            
if (xm[i] ==- 1 ) {
                memset(sy,
0 , sizeof (sy));
                cnt
+= _path(i);
            }

    }
 
}









posted on 2006-07-07 17:41 踏雪赤兔 阅读(4520) 评论(20)  编辑 收藏 引用 所属分类: 零件仓库速查手册

FeedBack:
# re: 标程:经典图算法
2006-08-07 18:52 | 踏雪赤兔
嗯~~这篇东东可以说是正宗的“旺丁不旺财”了~~近70的浏览量,却一个回复都没有,真没办法~~  回复  更多评论
  
# re: 标程:经典图算法
2006-08-08 11:12 | lester
哎,看不懂啊,我只对C#稍微懂一点点~也没学多长时间,这个上面的代码是C++吧  回复  更多评论
  
# re: 标程:经典图算法
2006-08-08 13:00 | 踏雪赤兔
是的,上述代码是C++语言描述,经VC和g++的编译器编译通过。  回复  更多评论
  
# re: 标程:经典图算法
2006-08-08 21:22 | lester
编译出来是干什么用的?  回复  更多评论
  
# re: 标程:经典图算法
2006-08-08 21:57 | 踏雪赤兔
  c++是编译型语言,即是源代码要经过编译器编译链接才能生成可执行程序。编译时编译器会检查语法。经过XX编译器通过表示了它符合该编译器的语法规范。这样解释可以了么?  回复  更多评论
  
# re: 标程:经典图算法
2006-08-09 10:22 | lester
我不是这个意思,我也知道源代码经过编译器编译才行(比如C#的源码需要用csc.exe编译),我的意思是,这个源代码编译出来以后是干什么用的?而不是问你编译器的用途,OK?  回复  更多评论
  
# re: 标程:经典图算法
2006-08-09 10:48 | 踏雪赤兔
这是图论算法的标程。也就是说,当你要开发一个系统或者做一条ACM竞赛题时,要用到这些算法时,直接粘贴上去就行了。上述算法都是一些久负盛名的经典算法,有很多应用。  回复  更多评论
  
# re: 标程:经典图算法
2006-11-02 11:35 | AC
鸡仔,我来回复一个啦
琴日搜索FLoyd,搜到一个BLOG,里边有一个"踏雪赤兔"的回复,于是链接过来,果然系你啊,哈哈
/////
学到野啊,THX!~
不过我未搞明Floyd果三个循环既原理...得闲话我知吖,呵呵  回复  更多评论
  
# re: 标程:经典图算法
2006-11-02 20:24 | 踏雪赤兔
呵呵~~有缘啊~~“踏雪赤兔”是我在集训队的“三国群”中的ID,也可以算是我的常用网名啦~~得闲多D支持哦~~  回复  更多评论
  
# re: 标程:经典图算法
2007-04-09 01:42 | scnu_ZNH
我们的癖好差不多耶!!!!!
不过,还没到达你这么专业..
我大一自学as..
大二自学了MFC,.net...
现在专攻AC..
我向你学习..
我们很近..
scnu_ZNH..
你应该知道我在哪个学校..
  回复  更多评论
  
# re: 标程:经典图算法
2007-04-09 18:53 | 踏雪赤兔
华师!对不对呢?^_^  回复  更多评论
  
# re: 标程:经典图算法
2007-04-10 01:14 | scnu_ZNH
系啊,以后有问题来你这问,你方便就给我回答,我还很菜,ACM刚入门,算法理解还很困难..忽忽..
中大的ACM很强耶.能教教小弟真感激不尽..  回复  更多评论
  
# re: 标程:经典图算法
2007-04-10 17:59 | 踏雪赤兔
一般一天之内我都会回复的~~
P.S.:中大ACM队是很强啊~不过偶还是很小白~不过我还认识一些魔王和骨灰级的人物嘛~
  回复  更多评论
  
# re: 标程:经典图算法
2007-12-15 09:41 | 123
不懂  回复  更多评论
  
# re: 标程:经典图算法
2008-11-15 16:08 | 光光GG
谢谢~~  回复  更多评论
  
# re: 标程:经典图算法[未登录]
2009-05-16 21:27 | wu
为什么不加上spfa 这不是也蛮经典的么 O(VE)  回复  更多评论
  
# re: 标程:经典图算法
2009-07-31 10:29 | 123
@scnu_ZNH
装B男  回复  更多评论
  
# re: 标程:经典图算法
2009-08-06 09:36 |
贴了一堆代码,却不说明 对应的算法解决的是怎么样的问题,真是失败的帖子  回复  更多评论
  
# re: 标程:经典图算法
2009-08-07 00:20 | Acumon
@囧
标程是用于在比赛时敲上去的程序,自然不会也不需要任何关于算法本身的说明。至于你要的说明,可以参考任何一本合格的算法书,比如《算法导论》  回复  更多评论
  
# re: 标程:经典图算法
2009-10-19 10:45 | 包成
能编译,怎么运行?不加说明,你以为网上都是你同学呀。  回复  更多评论
  
只有注册用户登录后才能发表评论。

百度空间| 见闻日记| 编程感悟
我的twitter


LOGO

自我介绍:百度厂基础平台车间的一名挨踢民工。擅长C++、算法、语言设计、分布式计算,也用过Java,Python, PHP,JS/AS等语言开发。请关注我的twitter (免翻墙版) 发QQ消息


添加到收藏夹 Locations of visitors to this page

常用链接

随笔分类(300)

随笔档案(274)

文章分类(38)

相册

收藏夹(54)

与博主互动

博客手拉手

搜索

  •  

积分与排名

  • 积分 - 321181
  • 排名 - 9

最新评论

阅读排行榜

评论排行榜