题解 P5544 【[JSOI2016]炸弹攻击1】

· · 题解

练习模拟退火的好题。

模拟退火板子学习可以自己左转BFS（Baidu-First-Search）。

按照套路，我们先随便选一组开始的答案坐标，然后模拟退火不断更新即可。

算当前答案，我们既然已经确定了炸弹的中心点，那么肯定会贪心一下，使得当前炸弹的波及范围半径尽可能大（在不误伤建筑和不超过和题目中的限制 R的情况下）。

算这个最大半径只需要枚举每一个建筑，算出建筑中心点和当前点的距离，然后再用这个距离减去建筑的半径 r_i，和 R 取min即可。换句话说，我们设当前点和第 i 个建筑中心的距离为 X_i，则 \min\{X_i-r_i,R\} 就是最大攻击半径。

然后枚举每一个敌人，看能攻击到多少即可。

注：这题求的是最大值，所以我们不一定接受的答案所对应的（当前答案减去上一次答案）del 小于0，所以我们把正常模拟退火求最小值的

if(exp(-del / ts) > (double)rand() / RAND_MAX)ansx = sumx, ansy = sumy, ans1 = ansnow;

改成

if(exp(-del / ts) < (double)rand() / RAND_MAX)ansx = sumx, ansy = sumy, ans1 = ansnow;

就完事了。

还有就是把坐标，距离等等都要开成double，尽量多跑几遍模拟退火加大得出最优解的概率。

code:

#include<bits/stdc++.h>
#define ll long long
#define rint register int
const int maxn = 5e5;
const int INF = 2e9;
int read(){
    int x = 0,f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
using namespace std;
int n, m, r, xb[maxn], yb[maxn], rb[maxn], xe[maxn], ye[maxn], ans;
double delta = 0.996, te = 1e-10;
double ansx, ansy;
void init(){
    ansx = 0, ansy = 0;
    n = read(), m = read(), r = read();
    for(int i = 1; i <= n; i++){xb[i] = read(); yb[i] = read(); rb[i] = read();}
    for(int i = 1; i <= m; i++){xe[i] = read(); ye[i] = read(); ansx += xe[i]; ansy += ye[i];}
    ansx /= m, ansy /= m;
}
double loca(double x1, double y1, double x2, double y2){
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int check(double x, double y){
    int anss = 0;
    double r_ = (double)r;

    for(int i = 1; i <= n; i++){
        r_ = min(r_, loca(x, y, xb[i], yb[i]) - (double)rb[i]);
    }
    for(int i = 1; i <= m; i++){
        if(loca(x, y, xe[i], ye[i]) <= r_)anss++; 
    }
    return anss;
}
void SA(){
    double ts = 11451.4;
    int ans1 = 0;
    while(ts > te){
        double sumx = ansx + ((rand() << 1) - RAND_MAX) * ts;
        double sumy = ansy + ((rand() << 1) - RAND_MAX) * ts;
        int ansnow = check(sumx, sumy);
        int del = ansnow - ans1;
        if(del > 0)ansx = sumx, ansy = sumy, ans1 = ansnow, ans = max(ansnow, ans);
        else if(exp(-del / ts) < (double)rand() / RAND_MAX)ansx = sumx, ansy = sumy, ans1 = ansnow;
        ts = ts * delta;
    }
}
void solve(){
    srand(time(0));
    init();
    SA();
    SA();
    SA();
    SA();
    SA();
    SA();//多跑几遍
    cout << ans;
    return;
}

signed main(){
    solve();
}