#include < cstring >
// 常量定义：
const   int  maxV = 100 ;
const   double  Inf = 1e100;
// const int Inf=2000000000;
// Graph类定义：
template < class  T >
class="tags" href="/tags/STRUCT.html" title=struct>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 < class="tags" href="/tags/LIST.html" title=list>list >
using  std::class="tags" href="/tags/LIST.html" title=list>list;
template < class  T >
class="tags" href="/tags/STRUCT.html" title=struct>struct  GraphList {
     int  v;
     int  e;
    class="tags" href="/tags/LIST.html" title=list>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 {
/**/ /* 解决：查找、打印桥
 *class="tags" href="/tags/SuanFa.html" title=算法>算法：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::class="tags" href="/tags/LIST.html" title=list>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 {
/**/ /* 解决：强分量
 *class="tags" href="/tags/SuanFa.html" title=算法>算法：Gabow——O(E)
 *输入：图(表)：g
 *输出：分量编号sc[]
  */
    GraphList < int >  g;
     int  cnt0, cnt1;
     int  sc[maxV]; // 分量编号
     int  pre[maxV];     // DFS顺序
     int  class="tags" href="/tags/PATH.html" title=path>path[maxV],pp; // class="tags" href="/tags/PATH.html" title=path>path栈
     int  stack[maxV],sp; // 栈

     void  _SCdfsR( int  w) {
        pre[w] = cnt0 ++ ;
        stack[sp ++ ] = w;
        class="tags" href="/tags/PATH.html" title=path>path[pp ++ ] = w;
         int  v; std::class="tags" href="/tags/LIST.html" title=list>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[class="tags" href="/tags/PATH.html" title=path>path[pp - 1 ]]  >  pre[v])  -- pp;
            }
        }
         if (class="tags" href="/tags/PATH.html" title=path>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
 *class="tags" href="/tags/SuanFa.html" title=算法>算法：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
 *class="tags" href="/tags/SuanFa.html" title=算法>算法：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 { //   
/**/ /* 解决：所有点对最短路径
 *class="tags" href="/tags/SuanFa.html" title=算法>算法：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 { // ，
/**/ /* 解决：二分图最大匹配
 *class="tags" href="/tags/SuanFa.html" title=算法>算法：匈牙利匹配(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  _class="tags" href="/tags/PATH.html" title=path>path( int  u) // 返回是否找到增广路
     {
         for ( int  v = 0 ;v < yv;v ++ )  if (g[u][v]  &&   ! sy[v]) { sy[v] = 1 ;
             if (ym[v] ==- 1   ||  _class="tags" href="/tags/PATH.html" title=path>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 += _class="tags" href="/tags/PATH.html" title=path>path(i);
            }
    }  
}