HDU 6150 Vertex Cover

本文由 Ocrosoft 于 2017-08-21 14:55:15 发表

Vertex Cover

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 256000/256000 K (Java/Others)
Total Submission(s): 527    Accepted Submission(s): 209
Special Judge

Problem Description
As we know, minimumvertexcover is a classical NP-complete problem. There will not be polynomial time algorithm for it unless P=NP.
You can see the definition of vertex cover in https://en.wikipedia.org/wiki/Vertex_cover.
Today, little M designs an “approximate” algorithm for vertex cover. It is a greedy algorithm. The main idea of her algorithm is that always choosing the maximum degree vertex into the solution set. The pseudo code of her algorithm is as follows:
We assume that the labels of the vertices are from 1 to n.

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;

As a theory computer scientist, you immediately find that it is a bad algorithm. To show her that this algorithm dose not have a constant approximate factor, you need to construct an instance of vertex cover such that the solution get by this algorithm is much worse than the optimal solution.
Formally, your program need to output a simple undirected graph of at most 500 vertices. Moreover, you need to output a vertex cover solution of your graph. Your program will get Accept if and only if the solution size get by the above algorithm is at least three times as much as yours. 

 

Input
There is no input.
 

Output
First, output two integer n and m in a line, separated by a space, means the number of the vertices and the number of the edges in your graph.
In the next m lines, you should output two integers u and v for each line, separated by a space, which denotes an edge of your graph. It must be satisfied that 1≤u,v≤n and your graph is a simple undirected graph.
In the next line, output an integer k(1≤k≤n), means the size of your vertex cover solution.
Then output k lines, each line contains an integer u(1≤u≤n) which denotes the label of a vertex in your solution. It must be satisfied that your solution is a vertex cover of your graph.
 

Sample Output
	
4 4 1 2 2 3 3 4 4 1 2 1 3
Hint
The sample output is just to exemplify the output format.
 

Solution
2017中国大学生程序设计竞赛 – 网络选拔赛

#define C11
#include <set>
#include <map>
#include <stack>
#include <string>
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
#include <climits>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <functional>
#ifdef C11
#include <tuple>
#include <regex>
#include <random>
#include <complex>
#endif
using namespace std;
/** const var def */
const double eps = 1e-8;
const int maxn = 1e7 + 10;
const int MAXN = maxn * 4;
const int MOD = 1000000007;
const double PI = 4 * atan(1.0);
/** type def */
typedef long long LL;
typedef pair<int, int> Pii;
typedef pair<LL, LL> Pll;
typedef vector<int> Vi;
typedef pair<double, double> Vec2;
#ifdef C11
using Vec3 = tuple<double, double, double>;
using Tp3 = tuple<int, int, int>;
#endif
/** easy def */
#define _link(x) x&&x
#define ms(a) memset(a,0,sizeof(a))
#define msr(a) memset(a,-1,sizeof(a))
/* first, second, position */
#define _f first
#define _s second
#define _p(_tp,_pos) get<_pos>(_tp)
/* operator */
Pii operator +(const Pii &x, const Pii &y) { return Pii(x.first + y.first, x.second + y.second); }
Pii operator -(const Pii &x) { return Pii(-x.first, -x.second); }
Pii operator -(const Pii &x, const Pii &y) { return x + (-y); }
Pii operator +=(Pii &x, const Pii &y) { return x = x + y; }
Pii operator -=(Pii &x, const Pii &y) { return x = x - y; }
#pragma region input&output
template<class T>inline T read(T &num)
{
	char CH; bool F = false;
	for (CH = getchar(); CH<'0' || CH>'9'; F = CH == '-', CH = getchar());
	for (num = 0; CH >= '0'&&CH <= '9'; num = num * 10 + CH - '0', CH = getchar());
	F && (num = -num);
	return num;
}
template<class T>inline T read()
{
	T num;
	return read(num);
}
#ifdef C11
template<class T, class... Args>inline int read(T &t, Args &...args)
{
	read(t);
	read(args...);
	return t;
}
#endif
template<class T> inline void print(T p, char ed = '\n')
{
	int stk[70], tp = 0;
	if (p < 0) { putchar('-'); p = -p; }
	if (!p) { putchar('0'); if (ed != '\0')putchar(ed); return; }
	while (p) stk[++tp] = p % 10, p /= 10;
	while (tp) putchar(stk[tp--] + '0');
	if (ed != '\0')putchar(ed);
}
#ifdef C11
template<class T, class... Args>inline void print(T t, Args ...args)
{
	print(t, '\0');
	if (sizeof...(args))putchar(' ');
	else putchar('\n');
	print(args...);
}
#endif
#pragma endregion

int main()
{
	int n = 21; // 左侧21个点
	print(91, n * n); // 右边70个点,共n^2条边(左侧点度数均为n)
	for (int i = 1, cnt = n, cur = n + 1; i <= n; i++)
	{
		cnt += n / i; // 新增n/i个点
		for (int L=1; cur <= cnt; cur++)
		{
			for (int j = 1; j <= i; j++) // 每个点连左侧i个点
				printf("%d %d\n", cur, L++);
			if (cur == cnt) // 最后一个点
				for (; L <= n; L++) // 除i个点外,再连左侧剩余的点
					printf("%d %d\n", cur, L);
		}
	}
	print(n); // 答案是左侧点
	for (int i = 1; i <= n; i++)print(i);
	return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » HDU 6150 Vertex Cover

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址