HDOJ 4582 - DFS spanning tree - DFS树，贪心

62 阅读 0 评论 41 点赞

我是靠谱客的博主朴素糖豆，最近开发中收集的这篇文章主要介绍HDOJ 4582 - DFS spanning tree - DFS树，贪心，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目大意：

给定一个N个点、M条边的无向图Graph，以及从点1开始进行DFS形成的树Tree，定义"T-Simple Circle"为Graph中的环，要求其中只含一条不属于Tree的边。

将Graph中的一些边进行染色，使得其中每个T-simple Circle都至少包含一条被染色的边，求最少需要染色的边数。

N≤2e3，M≤2e4

本题关键的一点在于Tree是一棵DFS生成树，这样Tree以外的边只可能将某个点与它在Tree中的祖先相连（用反证法可以证明，只有这样才能维持DFS树的性质）。

也就是说，每条Tree以外的边都相当于在DFS生成树上划定了一条深度单调递增（递减）的链，问题转化为：最少染色多少条边，可以使每条链上都至少有一条边被染色。

不难发现，对Tree以外的边进行染色的覆盖效率远小于对Tree上的边进行染色，因此只需考虑DFS生成树的边。

类比直线上的区间选点问题，本题也可以用类似的贪心思路。

题解：http://blog.csdn.net/sd_invol/article/details/9963741

直线上区间选点问题的证明：http://blog.csdn.net/dgq8211/article/details/7534776

C++11代码（貌似HDOJ可以交C++11？）：


1 #include <cstdio>

2 #include <cstring>

3 #include <algorithm>

4 #include <vector>

5 #include <functional>

6

7 const int maxN = 2000 + 5;

8 const int maxM = 20000 + 5;

9
 10 std::vector<int> toVec[maxN];
 11 int father[maxN]; //father in the DFS tree
 12 int depth[maxN]; //depth in the DFS tree
 13 bool covered[maxN]; //whether the edge (x - father[x]) is covered (used in greedy algorithm)
 14
 15 struct Range
 16 {
 17
int head, tail; //We guarantee that depth[head] >= depth[tail]
 18
 19
void swapEndPoint()
 20 
{
 21
if (depth[head] < depth[tail])
 22 
std::swap(head, tail);
 23 
}
 24
bool operator < (const Range& rhs) const
 25 
{
 26
return depth[tail] > depth[rhs.tail] ||
 27
(depth[tail] == depth[rhs.tail] && depth[head] < depth[rhs.head]);
 28
//high depth -> 0 --- 0 --- 0 --- 0 --- 0 -> low depth
 29
//greater:
x --------- x
 30
//less:
x --------------------- x
 31 
}
 32 };
 33
 34 Range range[maxM];
 35 int N, M;
 36
 37 void init()
 38 {
 39
memset(father, 0, sizeof(father));
 40
memset(depth, 0, sizeof(depth));
 41
memset(covered, 0, sizeof(covered));
 42
for (int i = 1; i <= N; i++)
 43 
toVec[i].clear();
 44 }
 45
 46 /// @brief swap head and tail so that depth[head] >= depth[tail]
 47 ///
this function is called after depth[] is set, before sorting ranges for greedy algorithm
 48 void initRange()
 49 {
 50
for (int i = 0; i < M - N + 1; i++)
 51 
range[i].swapEndPoint();
 52 }
 53
 54 bool input()
 55 {
 56
scanf("%d%d", &N, &M);
 57
if (N == 0)
 58
return false;
 59
 60 
init();
 61
for (int u, v, i = 0; i < N - 1; i++) //(N - 1) Edges in DFS tree
 62 
{
 63
scanf("%d%d", &u, &v);
 64 
toVec[u].push_back(v);
 65 
toVec[v].push_back(u);
 66 
}
 67
for (int u, v, i = N - 1; i < M; i++)
 68 
{
 69
scanf("%d%d", &u, &v);
 70
range[i - N + 1] = {u, v}; //The end points may be swapped later
 71 
}
 72
 73
return true;
 74 }
 75
 76 ///@brief DFS process, setting depth[] and father[]
 77 void dfs(int cur, int last)
 78 {
 79
father[cur] = last;
 80
depth[cur] = depth[last] + 1;
 81
for (auto to: toVec[cur])
 82 
{
 83
if (to == last)
 84
continue;
 85 
dfs(to, cur);
 86 
}
 87 }
 88
 89 ///@brief wrapper of DFS function
 90 void setDepthAndFather()
 91 {
 92
depth[0] = 0;
 93
dfs(1, 0);
 94 }
 95
 96 int solve()
 97 {
 98 
setDepthAndFather();
 99 
initRange();
100
std::sort(range, range + M - N + 1); //(M - N + 1) Edges that does not belong to the DFS tree
101
102
///@return last if edge (last, father[last]) should be covered
103
///
0 if no edge should be covered in this chain
104
auto getCoverEdge = [] (const Range& rg) -> int
105 
{
106
int last = rg.head;
107
108
//higher depth -> head -> tail -> lower depth
109
for (int cur = rg.head; cur != rg.tail; cur = father[cur])
110 
{
111
if (covered[cur])
112
return 0;
113
last = cur;
114 
}
115
return last;
116 
};
117
118 //
///@debug
119 //
for (int i = 1; i <= N; i++)
120 //
printf("father[%d] = %d, depth[%d] = %dn", i, father[i], i, depth[i]);
121
122
int ans = 0;
123
for (int i = 0; i < M - N + 1; i++)
124 
{
125
int coverId = getCoverEdge(range[i]);
126
if (coverId == 0)
127
continue;
128
ans += 1;
129
covered[coverId] = true;
130 
}
131
132
return ans;
133 }
134
135 int main()
136 {
137
while (input())
138
printf("%dn", solve());
139
return 0;
140 }