C++博客-Icyflame

割点与桥

Icyflame — Sun, 05 Jul 2009 08:18:00 GMT

一、定义
      割点：如果在图G中删去一个结点u后，图G的连通分枝数增加，即W(G-u)>W(G)，则称结点u为G的割点，又称关节点。
      桥：如果在图G中删去一条边e后，图G的连通分支数增加，即W(G-e)>W(G)，则称边u为G的桥，又称割边或关节边。
      双连通分支：G中不含割点的极大连通子图称为G的双连通分支，又称为G的块。
二、DFS
      描述：在对于任选一个图中结点为根的DFS搜索树中建立一个LAB数组与LOW数组，LAB数组存储个结点的编号，LOW数组存储各点及其子树的各结点能到达的最小编号结点的编号。

1 //lab为一个全局变量，初始为1， LAB各项初始为0
2 DFS(u)
3     LAB[u] = LOW[u] = lab++
4     for each (u, v) in E(G)
5         if LAB[v] is 0
6             DFS(v)
7             LOW[u] = min{LOW[u], LOW[v]}
8         else if  v isnot parent of u
9             LOW[u] = min{LOW[u], LAB[v]}

      第5行中，如果(u, v)是树边，则对v做深度优先搜索，并且LOW[u] = min{LOW[u], LOW[v]}，如果(u, v)是反向边，则LOW[u] = min{LOW[u], LAB[v]}。
三、割点
      描述：当一个结点u是割点时必满足以下两个条件之一：
            1）u为根且至少有两棵子树；
            2）u不为根且存在一个u在深搜树中的子女v使得LOW[v] ≥ LAB[u]。
      示例：POJ 1523 解题报告。
四、桥
       描述：一条边e=(u, v)是桥，当且仅当e为树枝边且LOW[v] > LAB[u]。
      示例：POJ 3352 解题报告。

Icyflame 2009-07-05 16:18 发表评论

POJ 3352 桥

Icyflame — Sun, 05 Jul 2009 08:08:00 GMT

一、题目描述

Description

It's almost summer time, and that means that it's almost summer construction time! This year, the good people who are in charge of the roads on the tropical island paradise of Remote Island would like to repair and upgrade the various roads that lead between the various tourist attractions on the island.

The roads themselves are also rather interesting. Due to the strange customs of the island, the roads are arranged so that they never meet at intersections, but rather pass over or under each other using bridges and tunnels. In this way, each road runs between two specific tourist attractions, so that the tourists do not become irreparably lost.

Unfortunately, given the nature of the repairs and upgrades needed on each road, when the construction company works on a particular road, it is unusable in either direction. This could cause a problem if it becomes impossible to travel between two tourist attractions, even if the construction company works on only one road at any particular time.

So, the Road Department of Remote Island has decided to call upon your consulting services to help remedy this problem. It has been decided that new roads will have to be built between the various attractions in such a way that in the final configuration, if any one road is undergoing construction, it would still be possible to travel between any two tourist attractions using the remaining roads. Your task is to find the minimum number of new roads necessary.

Input

The first line of input will consist of positive integers n and r, separated by a space, where 3 ≤ n ≤ 1000 is the number of tourist attractions on the island, and 2 ≤ r ≤ 1000 is the number of roads. The tourist attractions are conveniently labelled from 1 to n. Each of the following r lines will consist of two integers, v and w, separated by a space, indicating that a road exists between the attractions labelled v and w. Note that you may travel in either direction down each road, and any pair of tourist attractions will have at most one road directly between them. Also, you are assured that in the current configuration, it is possible to travel between any two tourist attractions.

Output

One line, consisting of an integer, which gives the minimum number of roads that we need to add.

Sample Input

Sample Input 1
10 12
1 2
1 3
1 4
2 5
2 6
5 6
3 7
3 8
7 8
4 9
4 10
9 10
Sample Input 2
3 3
1 2
2 3
1 3

Sample Output

Output for Sample Input 1
2
Output for Sample Input 2
0

二、分析
用DFS解决问题，详细算法：割点与桥。
三、代码

1#include<iostream>
2#include<list>
3using namespace std;
4int n, r;
5list<int> g[1001];
6int num, lab[1001], low[1001];
7list<pair<int, int> > edge;
8int degree[1001];
9int parent[1001], rank[1001];
10void init_set()
11{
12    for(int i=1; i<1001; i++)
13    {
14        parent[i] = i;
15        rank[i] = 1;
16    }
17}
18int find(int k)
19{
20    if(parent[k] == k)
21        return k;
22    else
23        return parent[k] = find(parent[k]);
24}
25void union_set(int u, int v)
26{
27    int pu = find(u), pv = find(v);
28    if(rank[pu] <= rank[pv])
29    {
30        parent[pu] = pv;
31        rank[pv] += pu;
32    }
33    else
34    {
35        parent[pv] = pu;
36        rank[pu] += pv;
37    }
38}
39void dfs(int u, int p)
40{
41    lab[u] = low[u] = num++;
42    list<int>::iterator it;
43    for(it = g[u].begin(); it != g[u].end(); it++)
44    {
45        int v = *it;
46        if(lab[v] == 0)
47        {
48            dfs(v, u);
49            low[u] = min(low[u], low[v]);
50            if(low[v] > lab[u])
51                edge.push_back(make_pair(u, v));
52            else
53                union_set(u, v); //u与v能进行缩点
54        }
55        else if(v != p)
56            low[u] = min(low[u], lab[v]);
57    }
58}
59int main()
60{
61    scanf("%d%d", &n, &r);
62    for(int i=1; i<=n; i++)
63        g[i].clear();
64    for(int i=1; i<=r; i++)
65    {
66        int v1, v2;
67        scanf("%d%d", &v1, &v2);
68        g[v1].push_back(v2);
69        g[v2].push_back(v1);
70    }
71    memset(lab, 0, sizeof lab);
72    memset(low, 0x7f, sizeof low);
73    num = 1;
74    init_set();
75    dfs(1, 0);
76    memset(degree, 0, sizeof degree);
77    list<pair<int, int> >::iterator it;
78    int res = 0;
79    for(it = edge.begin(); it != edge.end(); it++)
80    {
81        int u = it->first, v = it->second;
82        degree[find(u)]++;
83        if(degree[find(u)] == 1)
84            res++;
85        else if(degree[find(u)] == 2)
86            res--;
87        degree[find(v)]++;
88        if(degree[find(v)] == 1)
89            res++;
90        else if(degree[find(v)] == 2)
91            res--;
92    }
93    printf("%d\n", (res+1) / 2);
94}

Icyflame 2009-07-05 16:08 发表评论

POJ 1523 割点

Icyflame — Sat, 04 Jul 2009 08:12:00 GMT

一、题目描述

Description

Consider the two networks shown below. Assuming that data moves around these networks only between directly connected nodes on a peer-to-peer basis, a failure of a single node, 3, in the network on the left would prevent some of the still available nodes from communicating with each other. Nodes 1 and 2 could still communicate with each other as could nodes 4 and 5, but communication between any other pairs of nodes would no longer be possible.

Node 3 is therefore a Single Point of Failure (SPF) for this network. Strictly, an SPF will be defined as any node that, if unavailable, would prevent at least one pair of available nodes from being able to communicate on what was previously a fully connected network. Note that the network on the right has no such node; there is no SPF in the network. At least two machines must fail before there are any pairs of available nodes which cannot communicate.

Input

The input will contain the description of several networks. A network description will consist of pairs of integers, one pair per line, that identify connected nodes. Ordering of the pairs is irrelevant; 1 2 and 2 1 specify the same connection. All node numbers will range from 1 to 1000. A line containing a single zero ends the list of connected nodes. An empty network description flags the end of the input. Blank lines in the input file should be ignored.

Output

For each network in the input, you will output its number in the file, followed by a list of any SPF nodes that exist.

The first network in the file should be identified as "Network #1", the second as "Network #2", etc. For each SPF node, output a line, formatted as shown in the examples below, that identifies the node and the number of fully connected subnets that remain when that node fails. If the network has no SPF nodes, simply output the text "No SPF nodes" instead of a list of SPF nodes.

Sample Input

Sample Output

Network #1
SPF node 3 leaves 2 subnets
Network #2
No SPF nodes
Network #3
SPF node 2 leaves 2 subnets
SPF node 3 leaves 2 subnets

二、分析
用DFS解决问题，详细算法：割点与桥。
三、代码

1#include<iostream>
2#include<list>
3using namespace std;
4int t;
5int v1, v2;
6list<int> g[1001];
7bool flag;
8int root;
9int counter;
10bool spf[1001];
11int low[1001], lab[1001];
12bool visit[1001];
13void dfs(int u, int fa)
14{
15    low[u] = lab[u] = counter++;
16    list<int>::iterator it;
17    int counter = 0;
18    for(it = g[u].begin(); it != g[u].end(); it++)
19    {
20        int v = *it;
21        if(!lab[v])
22        {
23            counter++;
24            dfs(v, u);
25            low[u] = min(low[u], low[v]);
26            if((u==root && counter>=2) || (u!=root && low[v]>=lab[u]))
27                spf[u] = flag = true;
28        }
29        else if(v != fa)
30            low[u] = min(low[u], lab[v]);
31    }
32}
33void find(int u)
34{
35    visit[u] = true;
36    list<int>::iterator it;
37    for(it = g[u].begin(); it != g[u].end(); it++)
38        if(!visit[*it])
39            find(*it);
40}
41int main()
42{
43    t = 1;
44    while(1)
45    {
46        scanf("%d", &v1);
47        if(v1 == 0) break;
48        for(int i=1; i<=1000; i++)
49            g[i].clear();
50        memset(spf, 0, sizeof spf);
51        memset(low, 0, sizeof low);
52        memset(lab, 0, sizeof lab);
53        while(v1 != 0)
54        {
55            scanf("%d", &v2);
56            g[v1].push_back(v2);
57            g[v2].push_back(v1);
58            root = v1;
59            scanf("%d", &v1);
60        }
61        counter = 1;
62        flag = false;
63        dfs(root, -1);
64        printf("Network #%d\n", t++);
65        if(flag)
66        {
67            for(int i=1; i<=1000; i++)
68            {
69                if(!spf[i]) continue;
70                int cnt = 0;
71                memset(visit, 0, sizeof visit);
72                visit[i] = true;
73                list<int>::iterator it;
74                for(it = g[i].begin(); it != g[i].end(); it++)
75                    if(!visit[*it])
76                    {
77                        cnt++;
78                        find(*it);
79                    }
80                    printf("  SPF node %d leaves %d subnets\n", i, cnt);
81            }
82        }
83        else
84            printf("  No SPF nodes\n");
85        printf("\n");
86    }
87}

Icyflame 2009-07-04 16:12 发表评论

LCA问题（含RMQ的ST算法）

Icyflame — Sat, 04 Jul 2009 07:25:00 GMT

一、定义与定理
      LCA：Least Common Ancestors（最近公共祖先），对于一棵有根树T的任意两个节点u，v，求出LCA(T, u, v)，即离跟最远的节点x，使得x同时是u和v的祖先。
      在线算法：用比较长的时间做预处理，但是等信息充足以后每次回答询问只需要用比较少的时间。
      离线算法：先把所有的询问读入，然后一起把所有询问回答完成。
      RMQ：给出一个数组A，回答询问RMQ(A, i, j)，即A[i...j]之间的最值的下标。
二、DFS+RMQ
      1）Sparse Table（ST）算法
      描述：

1 //初始化
2 INIT_RMQ
3 //max[i][j]中存的是重j开始的i个数据中的最大值，最小值类似，num中存有数组的值
4     for i : 1 to n
5         max[0][i] = num[i]
6     for i : 1 to log(n)/log(2)
7         for j : 1 to n
8             max[i][j] = MAX(max[i-1][j], max[i-1][j+2^(i-1)]
9 //查询
10 RMQ(i, j)
11     k = log(j-i+1) / log(2)
12     return MAX(max[k][i], max[k][j-2^k+1])

      分析：初始化过程实际上是一个动态规划的思想。易知，初始化过程效率是O(nlogn)，而查询过程效率是O(1)。ST是一个在线算法。
      示例：POJ 3368 解题报告
      2）求解LCA问题
      描述：
      （1）DFS：从树T的根开始，进行深度优先遍历，并记录下每次到达的顶点。第一个的结点是root(T)，每经过一条边都记录它的端点。由于每条边恰好经过2次，因此一共记录了2n-1个结点，用E[1, ... , 2n-1]来表示。
      （2）计算R：用R[i]表示E数组中第一个值为i的元素下标，即如果R[u] < R[v]时，DFS访问的顺序是E[R[u], R[u]+1, ..., R[v]]。虽然其中包含u的后代，但深度最小的还是u与v的公共祖先。
      （3）RMQ：当R[u] ≥ R[v]时，LCA[T, u, v] = RMQ(L, R[v], R[u])；否则LCA[T, u, v] = RMQ(L, R[u], R[v])，计算RMQ。
      由于RMQ中使用的ST算法是在线算法，所以这个算法也是在线算法。
      示例：ZOJ 3195 解题报告。
三、Tarjan算法
      描述：Tarjan算法是一个离线算法，也就是说只有先获得所有的查询，再按一个特定的顺序进行运算。

1 //parent为并查集，FIND为并查集的查找操作
2 Tarjan(u)
3     visit[u] = true
4     for each (u, v) in QUERY
5         if visit[v]
6             ans(u, v) = FIND(v)
7     for each (u, v) in TREE
8         if !visit[v]
9             Tarjan(v)
10             parent[v] = u

示例：HDOJ 2586 解题报告。

Icyflame 2009-07-04 15:25 发表评论

HDOJ 2586 LCA:Tarjan

Icyflame — Thu, 02 Jul 2009 14:39:00 GMT

一、题目描述

Problem Description

There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.

Input

First line is a single integer T(T<=10), indicating the number of test cases.
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0 Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.

Output

For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.

Sample Input

Sample Output

二、分析
用Tarjan解决的LCA问题，详细算法：LCA问题。
三、代码

1#include<iostream>
2#include<list>
3using namespace std;
4struct node
5{
6    int v, d;
7    void init(int vv, int dd) {v = vv; d = dd;};
8};
9int t, n, m, v1, v2, len;
10list<node> g[40001];
11list<node> query[40001];
12int dis[40001];
13int res[201][3];
14int parent[40001];
15bool visit[40001];
16int find(int k)
17{
18    if(parent[k] == k)
19        return k;
20    return parent[k] = find(parent[k]);
21}
22void tarjan(int u)
23{
24    if(visit[u]) return;
25    visit[u] = true;
26    parent[u] = u;
27    list<node>::iterator it = query[u].begin();
28    while(it != query[u].end())
29    {
30        if(visit[it->v])
31            res[it->d][2] = find(it->v);
32        it++;
33    }
34    it = g[u].begin();
35    while(it != g[u].end())
36    {
37        if(!visit[it->v])
38        {
39            dis[it->v] = min(dis[it->v], dis[u] + it->d);
40            tarjan(it->v);
41            parent[it->v] = u;
42        }
43        it++;
44    }
45}
46int main()
47{
48    scanf("%d", &t);
49    while(t--)
50    {
51        scanf("%d%d", &n, &m);
52        for(int i=1; i<=n; i++)
53            g[i].clear();
54        for(int i=1; i<=m; i++)
55            query[i].clear();
56        for(int i=1; i<n; i++)
57        {
58            scanf("%d%d%d", &v1, &v2, &len);
59            node n1; n1.init(v2, len);
60            g[v1].push_back(n1);
61            node n2; n2.init(v1, len);
62            g[v2].push_back(n2);
63        }
64        for(int i=1; i<=m; i++)
65        {
66            scanf("%d%d", &v1, &v2);
67            res[i][0] = v1;
68            res[i][1] = v2;
69            node n1; n1.init(v2, i);
70            query[v1].push_back(n1);
71            node n2; n2.init(v1, i);
72            query[v2].push_back(n2);
73        }
74        memset(visit, 0, sizeof(visit));
75        memset(dis, 0x7f, sizeof(dis));
76        dis[1] = 0;
77        tarjan(1);
78        for(int i=1; i<=m; i++)
79            printf("%d\n", dis[res[i][0]] + dis[res[i][1]] - 2*dis[res[i][2]]);
80    }
81}

Icyflame 2009-07-02 22:39 发表评论

ZOJ 3195 LCA:RMQ

Icyflame — Thu, 02 Jul 2009 12:55:00 GMT

摘要: 一、题目描述 Cerror is the mayor of city HangZhou. As you may know, the traffic system of this city is so terrible, that there are traffic jams everywhere. Now, Cerror finds out that the main reason of the... 阅读全文

Icyflame 2009-07-02 20:55 发表评论

POJ 3368 RMQ

Icyflame — Wed, 01 Jul 2009 08:24:00 GMT

摘要: 一、题目描述 Description You are given a sequence of n integers a1 , a2 , ... , an in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ... 阅读全文

Icyflame 2009-07-01 16:24 发表评论

最小费用最大流问题

Icyflame — Tue, 30 Jun 2009 14:29:00 GMT

一、定义与定理
      最小费用最大流：设G是以s为源t为汇的网络，c是G的容量，b是G的单位流量费用，且有b[i][j] = -b[i][j]，f是G的流，则b(f)=∑(fij*bij)，(i, j)∈E(G) 且fij>0。最小费用最大流问题，就是求网络G的最大流f且使费用b(f)最小。这样的流称为最小费用最大流。
二、算法思想
      用Ford-Fulkerson算法的思想，不断地在残留网络中寻找增广路，只不过这个增广路是当前网络中s到t的以单位流量费用为权的最短路，对这条增广路进行操作。由于费用有负值，建议用SPFA算法。
三、算法介绍
      描述：

1 MCMF(G, s, t)
2     for each edge(u, v) in E(G)
3         do f[u, v] = 0
4            f[v, u] = 0
5     while exists a path p from s to t in Gf and p is the shortest path
6         do cf(p) = min{cf(u, v) : (u, v) in p}
7            for each edge(u, v) in p
8                do f[u, v] = f[u, v] + cf(p)
9                   f[v, u] = - f[u, v]

实现：

1mcmf()
2{
3    while(true)
4    {
5        for(int i=1; i<=n+m+1; i++)
6            d[i] = MAX;
7        d[s] = 0;
8        spfa(); //p中存有该点的前继点
9        if(p[t] == -1) //表示已无增广路
10            break;
11        int minf = INT_MAX;
12        int it = t;
13        while(p[it] != -1)
14        {
15            minf = min(minf, c[p[it]][it] - f[p[it]][it]);
16            it = p[it];
17        }
18        it = t;
19        while(p[it] != -1)
20        {
21            f[p[it]][it] += minf;
22            f[it][p[it]] = -f[p[it]][it];
23            it = p[it];
24        }
25    }
26}

三、算法示例
POJ 2516 解题报告

Icyflame 2009-06-30 22:29 发表评论

POJ 2516 最小费用最大流

Icyflame — Tue, 30 Jun 2009 14:09:00 GMT

摘要: 一、题目描述 Description Dearboy, a goods victualer, now comes to a big problem, and he needs your help. In his sale area there are N shopkeepers (marked from 1 to N) which stocks goods from him.Dearboy h... 阅读全文

Icyflame 2009-06-30 22:09 发表评论

匹配问题

Icyflame — Mon, 29 Jun 2009 06:48:00 GMT

一、定义与定理
      匹配：设G(V, E)为无环图，设M为E的一个非空子集，如果M中的任意两条边在G中不相邻，则称M是图G中的一个匹配。若对图G的任何匹配M'，均有|M'|≤|M|，则称M为G的最大匹配。
      饱和点：设M是图G中的匹配，G中与M中的边关联的顶点称为M饱和点，否则称为M非饱和点。若图中顶点均是M饱和点，则称M为G的完美匹配。
      M交错路：设P是G的一条路，且在P中，M的边和E-M的边交错出现，则称P是G的一条M交错路。若M交错路P的两个端点为M非饱和点，则称P为M可增广路。
      根在x的M交错子图：设x为G中M非饱和点。G中由起点为x的M交错路所能连接的顶点集所导出的G的导出子图。
      S的邻集：设S为G的任一顶点集，G中与S的顶点邻接的所有顶点的集合，称为S的邻集，记作N(S)。
      最优匹配：对于一个加权二部图，一个权最大的匹配叫作最优匹配。
      可行定标：映射l：V(G)→R，满足对G的每条边e={u, v}，均有l(u)+l(v)≥w(u, v)，其中w(u, v)表示边e的权，则称l为G的可行顶标。令El={(u, v) | {u, v}∈E(G)，l(u)+l(v)=w(u, v)}，Gl为以El为边集的G的生成子图，则称Gl为l等子图。
二、最大匹配（匈牙利算法）
      描述：
      （1）G是具有划分(V1, V2)的二分图，任给初始匹配M；
      （2）若M饱和V1则结束；
      （3）否则，在V1中找一M非饱和点，，置S={x}， T为空；
      （4）若N(S) = T，则停止，否则任选一点y∈N(S)-T；
      （5）若y为M非饱和点，则求一条从x到y的M可增广路P，置M为M异或P并转（2）；
      （6）否则，由于y是M的饱和点，故M中有一边{y, u}，置S = S∪{u}，T = T∪{y}，转（4）。
      实现：

1 HUNGARY
2     for i : 1 to |V2|
3         do match[i] = 0
4     for each vertex u in V1
5         do for i : 1 to |V2|
6                do visit[i] = false
7            DFS(u)
8 DFS(u)
9     for each vertex v in V2
10         if (u, v) in E(G) and visit[v] is false
11             then visit[v]=true
12                  if match[v] is 0 or DFS(match[v]) is true
13                      then match[v] = u
14                           return true
15     return false

      说明：第7行的DFS(u)过程，当存在从u开始的M可增广路，则返回true，并完成M的扩展，此时|M|加一。如果返回false，则表示不存在M可增广路。
      示例：POJ 1274 解题报告。
三、最优匹配（KM算法）
      描述：
      （1）从任意可行顶标l开始，确定l等子图Gl，并且在Gl中选取匹配M。若M饱和V1，则M是完美匹配，也即M是最优匹配，算法终止；
      （2）否则，运用匈牙利算法，终止于S属于V1，T属于V2且使对于Gl，N(S)=T。令al=min{l(x)+l(y)-w(x, y) | x∈S, y∈V2-T}，令l'(u)=l(u)-al如果u∈S；l'(u)=l(u)+al如果u∈T；l'(u)=l(u)，其它。用l'代替l，用Gl'代替Gl转入（1）。
      实现：

1 KUHN-MUNKRES(G)
2     for each vertex u in V1
3         do lx[u] = max{w[u][v] | (u, v) in E(G)}
4     for each vertex v in V2
5         do ly[v] = 0
6     for each vertex u in V1
7         do while(true)
8                do for each vertex u in V1
9                       do vx[u] = false
10                   for each vertex v in V2
11                       do vy[v] = false
12                          slack[v] = MAX
13                   if DFS(u) is true
14                       then break
15                   d = min{slack[v] | v in V2 and vy[v] is false}
16                   for each vertex u in V1
17                       do lx[u] = lx[u] - d
18                   for each vertex v in V2
19                       do ly[v] = ly[v] + d
20 DFS(u)
21     vx[u] = true
22     for each vertex v in V2
23         do if lx[u]+ly[v]==w[u][v] and vy[v] is false
24                then vy[v] = true
25                     if match[v] is NIL or DFS(match[v])
26                         then match[v] = u
27                              return true
28             else if lx[u]+ly[v]>w[u][v]
29                 then slack[v] = min{slack[v], lx[u]+ly[v]-w[u][v]}
30     return false

示例：POJ 2195 解题报告

Icyflame 2009-06-29 14:48 发表评论