//求割点
int dfs(int u, int fa)
{
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for(int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        if(!pre[v])
        {
            child++;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            //如果lowu==pre[v],光凭这一条u仍然是割点
            //>就更加了

            //lowv ,v及其后代能返回的最小祖先pre值，没有则返回自己 即lowv > pre[u] 则(u,v)是割边
            //而且还知道了u是割点
            if(lowv >= pre[u])
            {
                iscut[u] = true;
            }
        }
        else if(pre[v] < pre[u] && fa != v)//如果访问过就判断是不是后向边，
        {
            lowu = min(pre[v], lowu);
        }
    }
    //if(fa == -1 && child > 1) iscut[u] = true; 不这样判断是因为lowu一开始等于pre[u]
    if(fa < 0 && child == 1) iscut[u] = false;
    //如果是叶子结点，一开始是memset(iscut, 0, sizeof(iscut))

    low[u] = lowu;
    return lowu;
}



//求点双连通分量
struct Edge
{
    int u, v;
};

int pre[maxn], iscut[maxn], bccno[maxn], dfs_clock, bcc_cnt;//bccno记录每个点的bcc编号
vector  G[maxn], bcc[maxn];//bcc储存双连通分量的点
stack S;

int dfs(int u, int fa)
{
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for(int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        Edge e = (Edge){u, v};
        /*栈中存储的是边而不是点!!!*/
        /*因为割顶明显不可能属于任何一个点双，所以割顶的bccno无意义。*/
        if(!pre[v])
        {
            S.push(e);//没有访问过的，就压栈，把沿途遍历到的边都加入栈（也就是第一次遍历所有的点）
            child++;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if(lowv >= pre[u])//必存在割点  若大于则还存在割边(u, v)
            {
                //若发现了一个割点，说明当前栈中已经保存了点双的所有边。
                iscut[u] = true;
                bcc_cnt++;//从1开始
                bcc[bcc_cnt].clear();//清空准备储存
                for(;;)
                {
                    Edge x = S.top(); S.pop();
                    if(bccno[x.u] != bcc_cnt)
                    {
                        bcc[bcc_cnt].push_back(x.u);//第bcc_cnt个连通分量有点加入
                        bccno[x.u] = bcc_cnt;
                    }
                    if(bccno[x.v] != bcc_cnt)
                    {
                        bcc[bcc_cnt].push_back(x.v);
                        bccno[x.v] = bcc_cnt;
                    }
                    if(x.u == u && x.v == v) break;
                }//把边集中涉及到的点全部取出来，把他们的bccno[]设置成当前的bcc_cnt
            }
        }
        else if(pre[v] < pre[u] && v != fa)//反向边
        {
            S.push(e);//也许割点v此时被push
            lowu = min(lowu, pre[v]);//反向边更新
        }
    }
    if( fa < 0 && child == 1)   iscut[u] = 0;
    return lowu;
}

void find_bcc(int n)
{
    memset(pre, 0, sizeof(pre));
    memset(iscut, 0, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    dfs_clock = bcc_cnt = 0;
    for(int i = 0; i < n; i++)
        if(!pre[i]) dfs(i, -1);//怕万一有些点是孤立的
}

UVa 10801 电梯换乘

题意:

有5个以内电梯，分别可以到达不同的楼层，且速度不同，同一层次如果有两部电梯，就可以换乘，从一部电梯到任意一部电梯都花60s。求0层到某层花费的时间。

解法:

开始我想到的是把每一层不同的电梯看成一个点，但是建图会非常麻烦。看见网上题解用邻接矩阵，代码很简洁。
把每一层视为一个点，邻接矩阵储存每一个点i到另一个点j的最短距离，这个最短距离是未换乘的最短距离。任意i，j都是用了同一部电梯,但同一行或同一列不一定是同一部电梯。d[]刚好等价于G[0][]，接下来就是dijkstra算法，如：G0存在，说明0到i的最短距离就是G0，此时再更新所有邻接点，如果0，j无边，或者换乘后距离小于未换乘的最短距离，那就更新。
原代码在邻接点加了判断vis[y]是为了电梯可以一直向上走。

UVa 1664 Conquer a New Region

题意：

n个城镇，有n-1条路，c(i,j)表示两个城镇之间的交通容量，一条路径的容量的最大值是这条路径所有路的最小值，找出一个中心点，使得它到其他n-1个城镇的容量最大。

解法：

最小生成树的定义是边权总和最小的的生成树。这里并不是求边权总和最大的生成树，而是路径上权最小值，利用Kruskal算法，按照它排序做生成树。怎么求路径最小值？边从大到小排序，如果第一个是(u, v, c)，显然u到v的最小权值和v到u的都是等于c，对于新加入的边呢？新加入的(u, v1, c1)，和u，v属于同一个连通分量，那么c1肯定是u到v1和v到v1的最小权值，因为是从大到小排序。本来想的是计算每一个点的到其他点的权值和，然后排序找最大的，在每个连通分量添加新点时，更新他们的权值和，结果TLE。
看了网上类似贪心的做法，因为不需要求出具体哪个点作为中心，所以在每次添加新点时，比较两个点（孤立点或者连通分量代表元）谁作为中心时会更大，把并查集的代表元改为中心点。
其依据是：每加入一个点，由于排序，它的权值必然小于等于连通分量内所有边的权值，所以当新点作为中心点时，连通分量的每个点都必须加上新点带来的权值。

UVA 1279 Asteroid Rangers

题意：

n个点在三维空间，每个点会匀速移动，在xyz方向上有恒定速度，相同时间每个点都移动到不同坐标，图有唯一的最小生成树，且最小生成树在10^-6s内不会改变，求最小生成树的个数。

解法：

p1(x1 + dx1 t, y1 + dy1t, z1 + dz1 * t)
p2(x2 + dx2 t, y2 + dy2t, z2 + dz2 * t)

UVa Live 6039 Let’s Go Green

题意：

有n个城市，城市与城市构成树形结构（每个城市之间只有唯一一条路）简单起见，自行车不会走同样的路两次（一个城市路过一次），给出每条路上自行车经过的次数，求自行车最少能有多少。

解法1：

先求所有边的权的和sum，sum肯定是大于等于总单车数的，一辆车可以增加很多边权。把输入的单向边变为双向的，这样来遍历每一个点，这里把边权定义为经过边的单车数，让点权值等于经过该点的单车数，发现：点权和 = 边权和 + 最少单车数（难不成这是图论的某个定理？），点权的计算：如果有一条边的权比其余边权的和还要大，即maxm > esum – maxm，那么让这条边的单车往其他边走，点权（经过该点的单车）最少是maxm；如果没有出现这种情况，只能让边上的自行车的一半，经过该点然后去抵消另一半边，偶数自行车一半到另一半，奇数有一个在该点经过就不走了，剩下的一半去抵消另一半，对于整形除法都是(esum + 1) / 2。

这段时间的学习之后，掌握了容器、string类还有几个算法函数的基本用法，知道更多的字符串处理方法。

其中，不懂的题有：
K Smallest Sums

仍然还有bug的题有：
Borrowers
Updating a Dictionary
PGA Tour Prize Money
Bug Hunt

未做的题有：
The Letter Carrier’s Rounds
Do You Know the Way to San Jose?
Boring Game
USACO ORZ
Use of Hospital Facilities
Revenge of Fibonacci
Exchange
Queue and A