Description 如果某个无向连通图的任意一条边至多只出现在一条简单回路（simple cycle）里，我们就称这张图为仙人图（cactus）。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。 举例来说，上面的第一个例子是一张仙人图，而第二个不是——注意到它有三条简单回路：（4，3，2，1，6，5，4）、（7，8，9，10，2，3，7）以及（4，3，7，8，9，10，2，1，6，5，4），而（2，3）同时出现在前两个的简单回路里。另外，第三张图也不是仙人图，因为它并不是连通图。 显然，仙人图上的每条边，或者是这张仙人图的桥（bridge），或者在且仅在一个简单回路里，两者必居其一。定义在图上两点之间的距离为这两点之间最短路径的距离。定义一个图的直径为这张图相距最远的两个点的距离。现在我们假定仙人图的每条边的权值都是1，你的任务是求出给定的仙人图的直径。
早就开始做了。。。最近 czm 提起才想到。。。
首先求点双连通分量，然后对于每一个环 dp，可能的答案为 max{dis[i] + dis'[j], dis[x] + dist(x, y) + dis[y]}, dis 表示搜索树向下的最长路，dis‘表示第二长路（临时变量记之即可），dist(x, y) 表示仙人掌环上两点间的最短距离。
dp 就单（Ou）调（Shao）队列水过了。。。tarjan 什么的也就水过了。。。
然后爆栈什么的调了我一两个小时。。。最后删掉 dfs 中 3 个临时变量才过。。。
bzoj rank 10，貌似不是很颓。。。
Code :
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
#define FOR(i, j, k) for (i = (j); i <= (k); ++ i)
#define ROF(i, j, k) for (i = (j); i >= (k); -- i)
#define FER(i, j, k) for (i = j[k]; i; i = i->n)
#define maxn 50005
struct da{int t; da * n;};
da das[maxn * 4], * adj = das + 1, * edge[maxn];
int n, m, dfnn, tot, ans, i, j, k;
int dfn[maxn], low[maxn], dis[maxn];
da * sta[maxn * 2], ** top = sta;
int a[maxn * 2], q[maxn * 2], h, t;
void up(int & i, int j) {if (j > i) i = j;}
void down(int & i, int j) {if (j < i) i = j;}
void solve(int k)
{
int i; q[h = t = 1] = 1;
FOR (i, 2, tot)
{
while (i - q[h] > k) ++ h;
up(ans, dis[a[q[h]]] - q[h] + dis[a[i]] + i);
while (h <= t && dis[a[i]] - i > dis[a[q[t]]] - q[t]) -- t;
q[++ t] = i;
}
}
void dfs(int u, int fa)
{
da * e; int l = 0;
dfn[u] = low[u] = ++ dfnn;
FER (e, edge, u) if (e->t != fa)
if (dfn[e->t]) down(low[u], dfn[e->t]);
else
{
* (++ top) = e, dfs(e->t, u), down(low[u], low[e->t]);
if (low[e->t] > dfn[u])
{
-- top;
if (dis[e->t] + 1 > dis[u])
l = dis[u], dis[u] = dis[e->t] + 1;
else if (dis[e->t] + 1 > l)
l = dis[e->t] + 1;
}
else if (low[e->t] == dfn[u])
{
tot = j = 0;
do a[++ tot] = (* top)->t; while (* (top --) != e);
FOR (i, 1, tot)
{
up(j, dis[a[i]] + min(i, tot + 1 - i));
a[i + tot + 1] = a[i];
}
a[++ tot] = u, k = tot >> 1, tot = (tot << 1) - 1;
solve(k);
if (j > dis[u]) l = dis[u], dis[u] = j;
else if (j > l) l = j;
}
}
up(ans, l + dis[u]);
}
void link(int i, int j)
{
* (++ adj) = (da) {j, edge[i]}, edge[i] = adj;
* (++ adj) = (da) {i, edge[j]}, edge[j] = adj;
}
int main()
{
freopen("cactus.in", "r", stdin);
freopen("cactus.out", "w", stdout);
int u, v;
scanf("%d%d", & n, & m);
FOR (i, 1, m)
{
scanf("%d%d", & k, & u);
FOR (j, 2, k) scanf("%d", & v), link(u, v), u = v;
}
dfs(1, 0);
printf("%d\n", ans);
return 0;
}
本文发表于期刊《天津通信技术》2003年4期。
基于数据仓库和维度转换技术的广东电信公话IC话机话务动态分析系统
马根峰
(广东电信公用电话管理中心 广州
510635)
摘要 在电信市场尤其是公话市场竞争激烈的今天，广东电信公话中心的有关经营分析人员比较迫切的想进行众多IC话机话务的动态分析，即不但要能从较高层面上分析全省或某些地区、所有或部分话机类型、某些地区某些话机类型的话务在某些时间段的变化，而且要能从细节上跟踪每一部IC话机的200、IC话务在不同时期的变化。从而了解IC话机话务变化的原因或找出其中的规律，为管理者决策提供依据。但目前话机资料及话务数据分散于不同数据库表的组织方式确不能提供这样的支撑，所以必须对数据进行重新组织，并且要按照不同的分析需要对数据按照不同的综合程度来组织。然而话务的动态分析还要求对话机资料更新、对话务信息表按照时间维度进行转换，通常的OLAP分析工具在对几十万条记录的数据表进行维度转换时效率就极为低下。在这种前提下笔者编写了”话务动态分析系统”，利用数据仓库技术对数据源进行挖掘、按照不同的粒度来组织；在数据仓库设计时兼顾动态分析的需要，在数据仓库数据生成时自已编写程序实现话务按照时间维度转换，轻松地实现了话务的动态分析。
关键词 数据仓库；OLAP；维度；分布式数据库访问技术；事务
The system dynamic analyse of charge of pay phone for IC card in Public Payphone Center, Guangdong Telecom Corporation based on Data Warehousing & dimension conversion
MA Gen-feng
(Public Payphone Center, Guangdong Telecom Corporation, Guangzhou 510635)
ABSTRACT: Today, the competition becomes more severe in telecom market, especially in public pay phone market. The analyst in Public Payphone Center, Guangdong Telecom Corporation want to analyze the change of 200 & IC charge of many pay phone for IC card in different time as well as the influence on the change of the charge of all or part areas, all or part user types of pay phone, part areas and part user types of pay phone. If they do this they can find the reason for those change or the rule hide in those change so that they can support the decision-maker to make decision well. But the data of pay phone for IC card and the charge of them every month is distributed in many tables in database in On-Line operating environment now, it result in the huge difficulty to supply the analyst with sufficient proof to analyze the change of those charge above. So it is necessary to organize these data and store them in different integration level. What is more, it is necessary to update the information of pay phone and convert the time dimensionality because of the analysis above. While the OLAP tools for Data Warehousing shows quite low efficient in the process of this conversion of table with millions records well. So I develop a system to process the analysis of the change of the charge of two hundred thousand pay phone for IC card easily. In the system, it is the first step to dig the detail data of phones and those charge to the Data Warehousing, followed by the high efficient time dimensionality conversion of phones and those charge to a table then data in different integration level is created.
KEY WORDS:Data
Warehousing; OLAP; Dimensionality; Access to distributed Database; Transaction
1 引言
200及IC卡业务是广东电信的一项重要业务，因而对于众多IC话机上发生的200及IC话务分析显得非常必要。目前对于它们的分析主要包括层面比较高的地区级话务的变化以及某一计费月IC话机的话务情况。但经营分析人员即使知道了全省或部分地区的话务变化，却不能找出其中的原因或规律。这所以采取这样的分析方式，就是因为
莫非MAAS部署的OS与手动安装的OS有啥细微的差别，这些东西让开发者太失望了！
libvirt的版本为：0.9.8-2ubuntu17.4
ubuntu内核的版本为：Linux compute-63-30 3.2.0-35-generic #55-Ubuntu SMP Wed Dec 5 17:42:16 UTC 2012 x86_64 x86_64 x86_64 GNU/Linux
问题1：warning : lxcCapsInit:77 : Failed to get host power management capabilities
此错误为缺少电源管理的包，可忽略，也可通过安装电源管理相关的包解决。
sudo apt-get -y install pm-utils
问题2： error : lxcContainerMountDevFS:519 : Failed to mount /dev/pts in container: No such file or directory
此问题为符号链接（symbol link）引起的问题，即当container的配置文件中指定的container的rootfs的路径如在是在一个符号链接的目录下的话，就会报此问题，不用符号链接此问题可解决。
这些问题在我手动安装的ubuntu 12.04 server都没有出现，这太郁闷了！