HDU - 6150 构造题

最近的vj好垃圾，老崩，实名吐槽

题意：给出一个错误的求最小点覆盖的函数，需要来构造一组样例，使得那个函数跑出来的答案是正解的3倍以上。

很巧妙的构造技巧，首先想法就是弄一个二分图，让正确答案是上面的n个点，我们需要构造的就是下面的点，这就不知道为什么要这样构造了。也就是分块的思想。

从1~n每次分n/i个块，每个块的大小为i,对于每个块下面就构造出一个点跟块里所有点相连。

这样下面的点就是n+n/2+n/3+n/4+...大约就是nlnn个点，那我们要求nlnn>=3n，n>=27就可以了。

正确性上面，下面的点的度数为，1个为n的，n/(n-1)个位n-1的...n个位1的，这样每次都是优先选下面的点。

 #include<cstdio>

 #include<vector>

 using namespace std;

 typedef pair<int,int> pii;

 vector<pii> vv;

 int main(){

     int u=,v;

     for(int i=;i<=;i++){

         for(int j=;j</i;j++){

             u++;

             for(int k=;k<=i;k++){

                 v=i*j+k;

                 vv.push_back(pii(u,v));

             }

         }

     }

     printf("%d %d\n",u,(int)vv.size());

     for(int i=;i<vv.size();i++) printf("%d %d\n",vv[i].first,vv[i].second);

     printf("30\n");

     for(int i=;i<=;i++) printf("%d\n",i);

     return ;

 }

 #include<cstdio>

 #include<vector>

 using namespace std;

 const int N=;

 int vis[N],deg[N];

 vector<int> vv[N];

 int f(int n){

     int ans=;

     while(true){

         int mx=-,u;

         for(int i=;i<=n;i++){

             if(vis[i]) continue;

             if(deg[i]>=mx){

                 mx=deg[i];

                 u=i;

             }

         }

         if(mx<=) break;

         ans++;

         vis[u]=;

         for(int i=;i<(int)vv[u].size();i++) deg[vv[u][i]]--;

     }

     return ans;

 }

 int main(){

     int n,m,u,v;

     while(~scanf("%d%d",&n,&m)){

         while(m--){

             scanf("%d%d",&u,&v);

             vv[u].push_back(v);

             vv[v].push_back(u);

             deg[u]++;

             deg[v]++;

         }

         //for(int i=1;i<=30;i++) printf("%d\n",deg[i]);

         printf("%d\n",f(n));

     }

     return ;

 }

验证代码

巴特西

HDU - 6150 构造题

最新文章

热门文章