#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);
}
}
}
posted on 2006-07-07 17:41
踏雪赤兔 阅读(5166)
评论(20) 编辑 收藏 引用 所属分类:
零件仓库 、
速查手册