【链接】点击打开链接

【题意】

有人写了一个最小点覆盖的贪心算法,然后,让你去hack它。

并且,要求这个算法得到的错误答案,是正确答案的三倍。

让你任意输出hack数据,点数<=500

【题解】

最小点覆盖->二分图?

程序中有这么一段

        if (deg[i] >= mx) {

          mx = deg[i];

            u = i;

        }

也就是说,如果有多个度数最大的,它会选择标号最大的那一个。

这就是我们构造出答案的基础。

我们可以把二分图的左右两个部分各加N个点.

然后右边的点依次标号为N+1,N+2..2*N,左边从1..N

1和N+1,2和N+2...N和2N各连一条边。

这样,两边的点的度数都是1.

会优先选择右边那N个点.

接下来,我们要把右边的点的个数扩大到3N,且让程序仍然会优先选择右边的点。

可以这样,我们在右边再加一个点2*N+1,这个时候,我们让这个点和左边的点1,2各连一条边.

这样的话,2*N+1,1,2这3个点的度数都变成2了.然后程序依然会优先选择2*N+1这个点,然后把它删掉.

且删掉之后,剩余的点还是会优先选择右边的点(又变成全是度数为1的了)

说明这样没问题,那么我们接着选。

再选一个2*N+2,然后还是在左边选择点3,4,还是各连一条边。这样,3,4,2*N+2的度数又都变成2了.还是会

优先选择2*N+2.

...

依次类推,我们可以新加上一些点x,在左边连i个点,使得x的度数为i.

新加度数为i的点可以加N/i个;

选择N=50,就足够在右边造出3*N的点了。

【错的次数】

【反思】

最小点覆盖,应该早点想到二分图这个东西的。

要仔细阅读题目信息啊。

那个相同度数选最大的点的信息就很重要啊。

凭什么相同,你就选择最大的?这就是一个hack点.

【代码】

/*

*/

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

#include <map>

#include <queue>

#include <iomanip>

#include <set>

#include <cstdlib>

#include <cmath>

#include <bitset>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb emplace_back

#define fi first

#define se second

#define ld long double

#define ms(x,y) memset(x,y,sizeof x)

#define ri(x) scanf("%d",&x)

#define rl(x) scanf("%lld",&x)

#define rs(x) scanf("%s",x)

#define rf(x) scnaf("%lf",&x)

#define oi(x) printf("%d",x)

#define ol(x) printf("%lld",x)

#define oc putchar(' ')

#define os(x) printf(x)

#define all(x) x.begin(),x.end()

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

#define sz(x) ((int) x.size())

#define ld long double

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

//mt19937 myrand(time(0));

//int get_rand(int n){return myrand()%n + 1;}

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 50;

//const int X = 150;

vector <pii> v;

int r = N;

int main(){

    //Open();

    //Close();

    rep1(i,1,N) {

        r++;

        v.pb(mp(i,r));//两边之间各建一条边. 度数为1

    }

    rep1(d,2,N){//新加的点要建d条边到不同的点,这样这3个点度数都为d

        rep1(i,1,N/d){//一共能新建N/d个点

            r++;

            rep1(j,(i-1)*d+1,i*d)//和对应的范围分别连边

                v.pb(mp(j,r));

        }

        rep1(i,d*(N/d)+1,N) v.pb(mp(i,r));//后面会剩一部分,全都和r连上

    }

    oi(r),oc,oi(sz(v)),puts("");//输出n和m 边数没限制的,点数OK就行

    rep1(i,0,sz(v)-1)//按顺序输出每条边

        oi(v[i].fi),oc,oi(v[i].se),puts("");

    oi(N),puts("");//输出最小点覆盖

    rep1(i,1,N)

        oi(i),puts("");

    return 0;

}

巴特西

【2017中国大学生程序设计竞赛 - 网络选拔赛 hdu 6150】Vertex Cover