7
\*==================================================*/
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));
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]++;
}
}
/*==================================================*\
| 稳定婚姻问题 O(n^2)
\*==================================================*/
const int N = 1001;
struct People{
bool state;
int opp, tag;
int list[N]; // man使用
int priority[N]; // woman使用, 有必要的话可以和list合并，
以节省空间
void Init(){ state = tag = 0; }
}man[N], woman[N];
剩余44页未读，继续阅读
如风的吹风机
- 粉丝: 12
- 资源: 3
我的内容管理
展开
最新资源
- Vue实现iOS原生Picker组件：详细解析与实现思路
- Arduino蓝牙小车：参数调试与功能控制
- 百度Java面试精华：200页精选资源涵盖核心知识点
- Swift使用CoreData填坑指南：CoreData在Swift 3.0的变化
- 微距离无线充电器创新设计及其实验探索
- MTK Android平台开发全攻略：44步详解流程
- RecyclerView全面解析：替代ListView的新选择
- Android开发：自动适配中英文键盘解决方案
- Android调用WebService接口教程
- Android开发：BitmapUtil图片处理全解析与实例
- Android多线程断点续传实现详解
- PCA算法在人脸识别会议签到系统中的应用
- EventBus 3.0：Android事件总线详解与实战应用
- Android FileUtil：全面解析文件操作实用技巧与实例
- RecyclerView添加头部和尾部实战教程
- Android实现微博滑动固定顶部栏实战与优化
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
