题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6150
题意:"最小点覆盖集"是个NP完全问题 有一个近似算法是说—每次选取度数最大的点(如果有多个这样的点,则选择最后一个) 让你构造一个图,使得其近似算法求出来点数是你给定的覆盖点数的至少3倍。
解法:
可以把左边的点编号1~n,将左边的点进行n次分块,第i次分块中每块的大小为i,对于每一块的点,都在右边创建一个新节点与这些点相连。
①右边的点的度数为n,n-1,n-2,...,n/2,n/2,n/3,n/3,n/3....共有nlogn个点;
②左边的点的度数都不会超过n且只有一个点的度数为n
那么根据贪心算法,会把右边的点都删去,使得输出结果为nlogn,但正确的答案应该是取左边所有的点,只要n取个较大的数就可以使得nlogn>3n即可
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
pair<int,int>E[maxn];
int main()
{
int l=100,r=100,tot=0;
for(int i=2; i<=l; i++){
for(int j=0; j<l/i; j++){
++r;
for(int k=1; k<=i; k++){
E[++tot]=make_pair(r,i*j+k);
}
}
}
printf("%d %d\n", r, tot);
for(int i=1; i<=tot; i++) printf("%d %d\n", E[i].first, E[i].second);
printf("%d\n",l);
for(int i=1; i<=l; i++) printf("%d\n", i);
return 0;
}