HDU 6150 Vertex Cover 【构造】

发表于 | 更新于 | 分类于

题目大意：

最小顶点覆盖问题是一个传统的NP完全问题，就是多项式复杂程度的非确定性问题。现在告诉你一个此问题的近似解法，算法的主要思想是遍历每个顶点，贪心的选取当前未被选取的点中的与另外的点相连数目最多的顶点，相连数目相同时选序号靠后的那个点。伪代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
for (int i = 1; i <= n; ++i) {
  use[i] = false;
    deg[i] = degree of the vertex i;
}
int ans = 0;
while (true) {
  int mx = -1, u;
    for (int i = 1; i <= n; ++i) {
      if (use[i])
          continue;
        if (deg[i] >= mx) {
          mx = deg[i];
            u = i;
        }
    }
    if (mx <= 0)
      break;
    ++ans;
    use[u] = true;
    for (each vertex v adjacent to u)
      --deg[v];
}
return ans;

现在要你找出一组数据来，使得按照他的方法跑出来的结果是最优解的3倍以上。

解题思路：

题目中给出的思路显然是不对的，hack掉这个程序的关键就是当数目相同时他去掉的是靠后的那个点。

我们可以构造两组点，使得左边的那一组为正确答案，右边的为按照他的算法得出的答案。正确答案为左边，假设有n个点，先在右边构造n个点，和左边的一一相连；然后再在右边构造$\lfloor \frac{n}{2} \rfloor$个点，使得这些点依次与{1、2}、{3、4}……这些点相连，最后不足以连接的就不连；然后再在右边构造$\lfloor \frac{n}{3} \rfloor$个点，进行连接；……；直至构造了1个与n个点相连的点。

上面的构造方法就是根据前面的漏洞制定的，最后确定一下n为多少就好了。因为要求$3 * n \leq \sum_{i=1}^n{\lfloor \frac{n}{i} \rfloor}$, 所以n = 15就够了。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int L, R, cnt;
struct node
{
    int x, y;
}a[666];
int main()
{
    L = R = 15;
    //num就是构造的下一个点与左边集合的点相连数目
    for(int num = 1; num <= L; ++num)
    {
        //st为与左边相连的顶点的起点
        for(int st = 1; st <= L; st += num)
        {
            //要连的数目超过了左边顶点的数目
            if(st + num - 1 > L)   break;
            ++R;
            //开始将新构造的点与[st,st+num)间的点相连
            for(int t = st; t < st + num; ++t)
            {
                a[cnt].x = t;
                a[cnt].y = R;
                ++cnt;
            }
        }
    }
    printf("%d %d\n", R, cnt);
    for(int i = 0; i < cnt; ++i)
        printf("%d %d\n", a[i].x, a[i].y);
    printf("%d\n", L);
    for(int i = 1; i <= L; ++i)
        printf("%d\n", i);
    return 0;
}
Donate comment here
0%