題目描述

魔法炮來到了帝都，除了吃特色菜之外，還準備去嘗一嘗著名的北京烤鴨。帝都一共有n(1<=1<=100)個烤鴨店，可以看成是二維平面內的點。不過由于魔法炮在吃烤鴨之前沒有帶錢，所以吃完烤鴨之后只能留下刷盤子。刷完盤子之后，魔法炮除了不用付飯費之外，老板還會獎勵他d(1<=d<=10000)元錢。魔法炮是一個特么喜歡吃烤鴨的孩子，所以在去過一家烤鴨店之后，魔法炮還準備去其他的烤鴨店。但是由于帝都路費較貴，每單位長度需要花費1元錢，所以魔法炮可能去不了所有其他的烤鴨店。在到達下一家烤鴨店之前，魔法炮會花掉手里所有錢，以便于下一次接著吃霸王餐。另外，魔法炮對于自己刷過盤子的烤鴨店有著特殊的感情，所以他要求在某一家烤鴨店吃完烤鴨后，可以到達全部已經吃過去過的烤鴨店。那么問題來了，魔法炮想知道自己最多能去多少家烤鴨店，以及這些烤鴨店都是哪些。你能幫幫他嗎？

題目大意：給定平面內的n個點，選出一個點集S，使得S里的所有點兩兩之間歐幾里得距離不超過d，問|S|的最大值以及S里的點都有哪些。若答案有多種，輸出任意一個。 第一行兩個整數n和d，分別表示烤鴨店數和老板給魔法炮的路費。

輸入

接下來n行，每行兩個整數x,y，表示n個烤鴨店的坐標。

輸出

第一行一個數m，表示魔法炮最多能去多少家烤鴨店。

第二行m個數，每個數表示魔法炮能去的烤鴨店標號。

樣例輸入

4 1
0 0
0 1
1 0
1 1

樣例輸出

2
1 2

---

題解

隨機化

題意即求最大團，然而最大團是NPC問題。

對于這道題來說，可以使用隨機化算法：

首先想一個錯誤的貪心算法：對于每個點，能夠加入答案集合中就加入，否則不加人。

如果我們把這個序列進行大量的隨機排序，然后跑貪心算法，當進行次數較多時即可近似得到最優解。

給序列隨機排序可以使用algorithm中的random_shuffle函數，使用方法和sort函數方法相同。

由于本題點在二維平面上的特性，所以隨機次數不需要特別多，大概n^2次即可。

#include <cstdio> #include <cstring> #include <algorithm> #define N 110 using namespace std; int n , x[N] , y[N] , a[N] , map[N][N] , sta[N] , tot , ans[N] , sum; void cal() {int i , j;tot = 0;for(i = 1 ; i <= n ; i ++ ){for(j = 1 ; j <= tot ; j ++ )if(!map[a[i]][sta[j]])break;if(j > tot) sta[++tot] = a[i];}if(tot > sum){sum = tot;for(i = 1 ; i <= tot ; i ++ ) ans[i] = sta[i];} } int main() {int d , i , j;scanf("%d%d" , &n , &d);for(i = 1 ; i <= n ; i ++ ) scanf("%d%d" , &x[i] , &y[i]) , a[i] = i;for(i = 1 ; i <= n ; i ++ )for(j = 1 ; j <= n ; j ++ )if((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) <= d * d)map[i][j] = 1;for(i = 1 ; i <= n * n ; i ++ )random_shuffle(a + 1 , a + n + 1) , cal();printf("%d\n" , sum);for(i = 1 ; i <= sum ; i ++ ) printf("%d " , ans[i]);printf("\n");return 0; }

?

?

轉載于:https://www.cnblogs.com/GXZlegend/p/7245828.html

總結

以上是生活随笔為你收集整理的【bzoj4080】[Wf2014]Sensor Network 随机化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。