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页未读，继续阅读
XXXGFXXX
- 粉丝: 8
- 资源: 9
我的内容管理
展开
最新资源
- 前端面试必问：真实项目经验大揭秘
- 永磁同步电机二阶自抗扰神经网络控制技术与实践
- 基于HAL库的LoRa通讯与SHT30温湿度测量项目
- avaWeb-mast推荐系统开发实战指南
- 慧鱼SolidWorks零件模型库：设计与创新的强大工具
- MATLAB实现稀疏傅里叶变换(SFFT)代码及测试
- ChatGPT联网模式亮相，体验智能压缩技术.zip
- 掌握进程保护的HOOK API技术
- 基于.Net的日用品网站开发：设计、实现与分析
- MyBatis-Spring 1.3.2版本下载指南
- 开源全能媒体播放器：小戴媒体播放器2 5.1-3
- 华为eNSP参考文档：DHCP与VRP操作指南
- SpringMyBatis实现疫苗接种预约系统
- VHDL实现倒车雷达系统源码免费提供
- 掌握软件测评师考试要点：历年真题解析
- 轻松下载微信视频号内容的新工具介绍
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
