吉林大学 ACM Group
7
| 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 &&
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; // 强连通分量的个数
}
/*==================================================*\
| 弦图判断
| 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 as the following:
\*==================================================*/
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));