graph.cpp
来自「ACM经典算法ACM经典算法ACM经典算法」· C++ 代码 · 共 590 行 · 第 1/2 页
CPP
590 行
return 1;
}
/*============================================================*\
| Johnson所有点对最短路 |
\*============================================================*/
Johnson(G)
compute G' where V[G'] = V[G] + {s} and
E[G'] = E[G] + {(s, v) : v in V[G]}
IF Bellman-ford(G', w, s) = false THEN
G has a negative-weight cycle.
ELSE FOR each vertex v in V[G'] DO
set h[v] = d(s, v)
FOR each edge (u, v) in E[G'] DO
w'(u, v) = w(u, v) + h[u] - h(v)
FOR each vertex u in V[G] DO
run Dijkstra(G, w', u) to compute
d'(u, v) for all v in V[G]
FOR each vertex v in V[G] DO
D[u][v] = d'[u, v] + h[v] - h[u]
return D[][]
/*============================================================*\
| Prim求MST |
| INIT: cost[][]耗费矩阵(inf为无穷大); |
| CALL: prim(cost, n); 返回-1代表原图不连通; |
\*============================================================*/
#define typec int // type of cost
const typec inf = 0x3f3f3f3f; // max of cost
int vis[V]; typec lowc[V];
typec prim(typec cost[][V], int n) // vertex: 0 ~ n-1
{
int i, j, p;
typec minc, res = 0;
memset(vis, 0, sizeof(vis));
vis[0] = 1;
for (i=1; i<n; i++) lowc[i] = cost[0][i];
for (i=1; i<n; i++) {
minc = inf; p = -1;
for (j=0; j<n; j++) if (0 == vis[j] && minc > lowc[j]) {
minc = lowc[j]; p = j;
}
if (inf == minc) return -1; // 原图不连通
res += minc; vis[p] = 1;
for (j=0; j<n; j++)
if (0 == vis[j] && lowc[j] > cost[p][j])
lowc[j] = cost[p][j];
}
return res;
}
/*============================================================*\
| 有向图最小树形图 |
| INIT: eg置为边表; res置为0; cp[i]置为i; |
| CALL: dirtree(root, nv, ne); res是结果; |
\*============================================================*/
#define typec int // type of res
const typec inf = 0x3f3f3f3f; // max of res
typec res, dis[V];
int to[V], cp[V], tag[V];
struct Edge { int u, v; typec c; } eg[E];
int iroot(int i)
{
if (cp[i] == i) return i;
return cp[i] = iroot(cp[i]);
}
int dirtree(int root, int nv, int ne) // root: 树根
{
int i, j, k, circle = 0;
memset(tag, -1, sizeof(tag));
memset(to, -1, sizeof(to));
for (i = 0; i < nv; ++i) dis[i] = inf; // vertex: 0 ~ n-1
for (j = 0; j < ne; ++j) {
i = iroot(eg[j].u); k = iroot(eg[j].v);
if (k != i && dis[k] > eg[j].c) {
dis[k] = eg[j].c;
to[k] = i;
}
}
to[root] = -1; dis[root] = 0; tag[root] = root;
for (i = 0; i < nv; ++i) if (cp[i] == i && -1 == tag[i]) {
j = i;
for ( ; j != -1 && tag[j] == -1; j = to[j]) tag[j] = i;
if (j == -1) return 0;
if (tag[j] == i) {
circle = 1; tag[j] = -2;
for (k = to[j]; k != j; k = to[k]) tag[k] = -2;
}
}
if (circle) {
for (j = 0; j < ne; ++j) {
i = iroot(eg[j].u); k = iroot(eg[j].v);
if (k != i && tag[k] == -2) eg[j].c -= dis[k];
}
for (i = 0; i < nv; ++i) if (tag[i] == -2) {
res += dis[i]; tag[i] = 0;
for (j = to[i]; j != i; j = to[j]) {
res += dis[j]; cp[j] = i; tag[j] = 0;
}
}
if (0 == dirtree(root, nv, ne)) return 0;
} else {
for (i = 0; i < nv; ++i) if (cp[i] == i) res += dis[i];
}
return 1; // 若返回0代表原图不连通
}
/*============================================================*\
| Minimal Steiner Tree |
| G(V, E), A是V的一个子集, 求至少包含A中所有点的最小子树. |
| 时间复杂度: O(N^3 + N * 2^A * (2^A + N)) |
| INIT: d[][]距离矩阵; id[]置为集合A中点的标号; |
| CALL: steiner(int n, int a); |
| main()函数解决的题目: Ticket to Ride, NWERC 2006/2007 |
| 给4个点对(a1, b1) ... (a4, b4), 求min(sigma(dist[ai][bi])) |
| 其中重复的路段只能算一次. |
| 这题要找出一个steiner森林, 最后要对森林中树的个数进行枚举 |
\*============================================================*/
#define typec int // type of cost
const typec inf = 0x3f3f3f3f; // max of cost
int vis[V], id[A]; // id[]: A中点的标号
typec d[V][V], dp[1<<A][V]; // dp[i][v]: 点v到点集i的最短距离
void steiner(int n, int a)
{
int i, j, k, mx, mk, top = (1 << a);
for (k = 0; k < n; k++) for (i = 0; i < n; i++)
for (j = 0; j < n; j++) if (d[i][j] > d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j];
for (i = 0; i < a; i++) { // vertex: 0 ~ n-1
for (j = 0; j < n; j++)
dp[1 << i][j] = d[j][ id[i] ];
}
for (i = 1; i < top; i++) {
if ( 0 == (i & (i - 1)) ) continue;
memset(vis, 0, sizeof(vis));
for (k = 0; k < n; k++) { // init
for (dp[i][k] = inf, j = 1; j < i; j++)
if ((i | j) == i)
if (dp[i][k] > dp[j][k] + dp[i - j][k])
dp[i][k] = dp[j][k] + dp[i - j][k];
}
for (j = 0; mx = inf, j < n; j++) { // update
for (k = 0; k < n; k++)
if (dp[i][k] <= mx && 0 == vis[k])
mx = dp[i][mk = k];
for (k = 0, vis[mk] = 1; k < n; k++)
if (dp[i][mk] > dp[i][k] + d[k][mk])
dp[i][mk] = dp[i][k] + d[k][mk];
}
}
}
int main(void)
{
int n, a = 8;
// TODO: read data;
steiner(n, a);
// enum to find the result
for (i = 0, b = inf; z = 0, i < 256; b > z ? b = z : b, i++)
for (j = 0; y = 0, j < 4; z += !!y * dp[y][x], j++)
for (k = 0; k < 8; k += 2) if ((i >> k & 3) == j)
y += 3 << k, x = id[k];
// TODO: cout << b << endl;
return 0;
}
/*============================================================*\
| Tarjan强连通分量 |
| INIT: vec[]为邻接表; stop, cnt, scnt置0; pre[]置-1; |
| CALL: for (i=0; i<n; ++i) if (-1 == pre[i]) tarjan(i, n); |
\*============================================================*/
vector<int> vec[V];
int id[V], pre[V], low[V], s[V], stop, cnt, scnt;
void tarjan(int v, int n) // vertex: 0 ~ n-1
{
int t, minc = low[v] = pre[v] = cnt++;
vector<int>::iterator pv;
s[stop++] = v;
for (pv = vec[v].begin(); pv != vec[v].end(); ++pv) {
if(-1 == pre[*pv]) tarjan(*pv, n);
if(low[*pv] < minc) minc=low[*pv];
}
if(minc < low[v]) {
low[v] = minc; return;
}
do {
id[t = s[--stop]] = scnt; low[t] = n;
} while(t != v);
++scnt; // 强连通分量的个数
}
/*============================================================*\
| 2-sat问题 |
| n个集团, 每个集团2个人, 现在要选出n个人当代表, 且每个集团|
| 只能选出一个人. 如果两人有矛盾, 他们不能同时被选中, 求一组 |
| 可行解. |
\*============================================================*/
构造有向图G. G包含2n个顶点, 代表2n个人. 于是问题转化为从G中
选出n个顶点, 使其满足2-sat条件. 当存在矛盾边(i, j)时, 表示当选
择i时, 必须选择j', 同样当选择j时, 必须选择i'. 于是向G中添加两
条弧: (i, j')和(j, i').
1. 求G的所有强连通分量. 很明显, 如果我们选中强连通分量中的
任一点, 那么该强连通分量中的其它点也必须被选中. 如果i和i'属于
同一强连通分量, 则矛盾产生, 该2-sat无解.
2. 若无矛盾, 把处于同一强连通分量中的点和边缩成一个点, 得到
图G'. 现在G'肯定不存在圈.
3. 把G'中的所有点置为未着色, 按照拓扑顺序重复下面操作:
i. 选择第一个未着色顶点x, 把x染成红色;
ii. 把所有与x矛盾的点y及y的所有子孙全部染成蓝色;(若存
在<i, i'>, 其中i属于x, i'属于y, 则x与y矛盾)
iii.重复i和ii, 直至结束.
iv. G'中被染成红色的点对应的G中的点集, 就是该2-sat的一个解.
/*============================================================*\
| 弦图判断 |
| INIT: g[][]置为邻接矩阵; |
| CALL: mcs(n); peo(n); |
| 第一步: 给节点编号 mcs(n) |
| 设已编号的节点集合为A, 未编号的节点集合为B |
| 开始时A为空, B包含所有节点. |
| for num=n-1 downto 0 do { |
| 在B中找节点x, 使与x相邻的在A集合中的节点数最多, |
| 将x编号为num, 并从B移入A. |
| } |
| 第二步: 检查 peo(n) |
| for num=0 to n-1 do { |
| 对编号为num的点x, 设所有编号>num且与x相邻的点集为C |
| 在C中找出编号最小的节点y, |
| 若C中存在点z!=y, 使得y与z之间无边, 则此图不是弦图. |
| } |
| 检查完了, 则此图是弦图. |
\*============================================================*/
int g[V][V], order[V], inv[V], tag[V];
void mcs(int n)
{
int i, j, k;
memset(tag, 0, sizeof(tag));
memset(order, -1, sizeof(order));
for (i = n - 1; i >= 0; i--) { // vertex: 0 ~ n-1
for (j = 0; order[j] >= 0; j++) ;
for (k = j + 1; k < n; k++)
if (order[k] < 0 && tag[k] > tag[j]) j = k;
order[j] = i, inv[i] = j;
for (k = 0; k < n; k++) if (g[j][k]) tag[k]++;
}
}
int peo(int n)
{
int i, j, k, w, min;
for (i = n - 2; i >= 0; i--) {
j = inv[i], w = -1, min = n;
for (k = 0; k < n; k++)
if (g[j][k] && order[k] > order[j] && order[k] < min)
min = order[k], w=k;
if (w < 0) continue;
for (k = 0; k < n; k++)
if (g[j][k] && order[k] > order[w] && !g[k][w])
return 0; // no
}
return 1; // yes
}
/*============================================================*\
| 弦图的perfect elimination点排列 |
| INIT: g[][]置为邻接矩阵; |
| CALL: cardinality(n); tag[i]为排列中第i个点的标号; |
| The graph with the property mentioned above is called |
| chordal graph. A permutation s = [v1 , v2 ,..., vn] of the |
| vertices of such graph is called a perfect elimination |
| order if each vi is a simplicial vertex of the subgraph |
| of G induced by { vi ,..., vn}. A vertex is called |
| simplicial if its adjacency set induces a complete |
| subgraph, that is, a clique (not necessarily maximal). |
| The perfect elimination order of a chordal graph can be |
| computed with the following codes: |
\*============================================================*/
procedure maximum cardinality search(G, s)
for all vertices v of G do
set label[v] to zero
end for
for all i from n downto 1 do
choose an unnumbered vertex v with largest label
set s(v) to i{number vertex v}
for all unnumbered vertices w adjacent to vertex v do
increment label[w] by one
end for
end for
end procedure
int tag[V], g[V][V], deg[V], vis[V];
void cardinality(int n)
{
int i, j, k;
memset(deg, 0, sizeof(deg));
memset(vis, 0, sizeof(vis));
for (i = n - 1; i >= 0; i--) {
for (j = 0, k = -1; j < n; j++) if (0 == vis[j]) {
if (k == -1 || deg[j] > deg[k]) k = j;
}
vis[k] = 1, tag[i] = k;
for (j = 0; j<n; j++)
if (0 == vis[j] && g[k][j]) deg[j]++;
}
}⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?