description.txt

关于经典图论的算法

#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 != i  &&  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);
            } 
    }  
}